If you're seeking wild trout, your first question is always, "Are there trout there?".  Your second, if you're a law abiding citizen, which most of us are, is, "Can I get access?"  In much of the country, and especially out west, the Federal Government may own the land.  Parks and wilderness areas will always be open to the public, whereas BLM or NF lands may be leased or closed for various reasons.  So you'll want to check with the appropriate management agency before showing up to fish unless you know for a fact that the area is open.

The image shows this incredibly useful layer, which will definitively answer the question of whether a stream is on Federal land.  It is the product of an organization called the "Surface Management Agency" which apparently coordinates among the various (and highly confusing) federal agencies that manage land including the Department of the Interior (BLM, BIA, and NPS), Department of Agriculture (USFS), and Department of Defense.  In the image, BLM-managed land is shown yellow; Indian reservations are beige, National Forest land is green, and National Parks are Lavender.  Note that Indian reservations regulate fishing independent of the states in which they're located.  So if you're interested in streams on Indian land, you'll need to check the regulations for the reservation, and will need to acquire a permit from them (state licenses aren't required).

Where the layer gets truly useful is at high resolutions (see image below).  Here we see a segment of northern Nevada.  Red streams are from the Nevada Redband trout dataset.  You can see that almost all of the streams are located either within Humboldt National Forest or on BLM land.  However, especially on BLM land, some streams have substantial private in-holdings (these are the dark cutouts where you see the base layer).  Wheras the federally owned lands are likely open to fishing, the private lands could be fenced and/or posted.  So it's useful to check this layer as part of your due diligence, and call the regional HQ of either BLM or the Forest Service to confirm access.

Source (both images):  KLM by Surface Management Agency.  Image in Google Earth.