How to search for a specific message?
There are several ways for this, too. For a posting from a Usenet group the easiest solution is probably to ask groups.google.com, if you found the posting there, tell Google to display the raw message, look for the message-id, and say ‘M-^ email@example.com RET’ in a summary buffer. Since Gnus 5.10 there's also a Gnus interface for groups.google.com which you can call with ‘G W’) in group buffer.
Another idea which works for both mail and news groups is to enter the group where the message you are searching is and use the standard Emacs search ‘C-s’, it's smart enough to look at articles in collapsed threads, too. If you want to search bodies, too try ‘M-s’ instead. Further on there are the gnus-summary-limit-to-foo functions, which can help you, too.
Of course you can also use grep to search through your local mail, but this is both slow for big archives and inconvenient since you are not displaying the found mail in Gnus. Here nnir comes into action. Nnir is a front end to search engines like swish-e or swish++ and others. You index your mail with one of those search engines and with the help of nnir you can search through the indexed mail and generate a temporary group with all messages which met your search criteria. If this sounds cool to you, get nnir.el from ftp://ftp.is.informatik.uni-duisburg.de/pub/src/emacs/. Instructions on how to use it are at the top of the file.