The plugin details seems easiest but they are say "packet" and not http request and not necessarily by a browser. Presuming they have compromised the machine this staining will be affecting the network stack somehow most likely at an IP level.

Yeah, while the Post seems to be talking about the user agent string, I don't think that's what they used, the Post just misinterpreted the document's use of the phrase User Agent to refer to the browser.

Indeed http://en.wikipedia.org/wiki/User_agent

Some slides on a way to do this: http://prezi.com/p5et9yawg2c6/ip-packet-staining/

Their solution was to re-route traffic to a package management device which clamps on a stain. Ipv6 makes this easy, if the traffic is Ipv4 they tunnel it inside Ipv6 with the stain header in Destination Option header.

Not sure how you would prevent this, besides the obvious answer (dont visit terrorist forums). Jondonym routing traffic through 3 mix servers might help so long as they don't stain your traffic at source by compromising your system. Making your own Tor bridge node is another solution to at least have some sort of safe entrance into the network. Seems they are unwilling to exploit relay nodes and bridges in the leaked slides.

and this naturally comes to mind:

https://tools.ietf.org/html/rfc3514

There are probably a lot of 0days that are judiciously used to exploit the browsers of people they're interested in, similar to the one used against the TBB a few months ago. This exploit probably just quietly modifies the UA string, appending something like a GUID. The victim then leaves a nice little Hansel & Gretel trail of breadcrumbs that can be picked up by GCHQ black box intercepts at POPs.

One of the documents from Guardian released yesterday mentioned evercookie in one of the bulleted lists. If this is more "request" level than packet level, that could be the method they are using - http://en.wikipedia.org/wiki/Evercookie

It's most likely just an error in terminology. They likely mean request instead of packet as the user-agent isn't in every packet.

If it was packet level it would likely be in the IP headers, I don't imagine it would be that difficult to rewrite the packets with optional fields and then put a token in the optional headers.