GPO has recently released a new series of training video modules on its Federal Digital System (FDsys). The first video introduces the basic search in FDsys and I must say that I was quite impressed.
The basic search is actually very powerful. It allows you to use Boolean operators (and, or, not) as well as quotes to search a phrase, proximity operators (near, before, adj) and parentheses to group searches.
The search results page features some very nice filtering options which allow you to narrow your search by collection, date, author, organization, etc.
The video is on the longer side for a tutorial (11 minutes), but if you search for federal government materials on a regular basis, it is well worth the time.