Fish Locally: I always find it strange that people insist on driving hours before they fish, when almost anywhere you live fly fishing can be found close at hand. Even in your major metropolitan areas, there are some urban streams that have fishing opportunities. While they might not be pristine, they are close, and usually under fished. The advantage of these local fisheries are they are easily accessible and can be fished multiple times in a month. Thereby increasing your fishing time. If you meet other fishermen, or if crowds are a problem you can begin to get a sense of when the times of the day, or year they are empty and concentrate on fishing during these times. Steelhead and bass in particular seem to run or live in metro areas, while steelhead just return to spawn it is still amazing what they put up with in their native waters.
Seasons, hatches, etc: The most famous rivers have famous hatches and runs on them. They are well known and marked on many a fisherman's calendar. Try fishing the edges of these times. For example, if the river of your desire has a Green Drake hatch that runs from the middle of May to the end of June, show up a week early. The big crowds are likely to hit right after the middle of May, people taking a week off of work, usually want to ensure the hatch will be going, so they tend to hit the middle of calendar period. By showing up early you are beating the crowd, and the fish are primed for the hatch, and the hatch itself just might be early. Likewise if you are fishing a run of steelhead that traditionally show up mid-March, and run strong through mid-May, beat the crowds by showing up the first week of March, and hope the fish are early, or work the water for the first fish of the season. Fish and hatches don't keep calendars, we can definitely use weather and water temperatures to predict peaks of runs and hatches but the fringes are imprecise, and fishing these times do result in fish. Late timing also works well, after the hatch has peaked or the runs have peaked there are still fish to be had. Think of a bell curve, the numbers might be down but so are the crowds.
Holes, Rivers, Runs: Like hatches and runs, famous rivers have holes, pools, stretches, that are pounded year after year. Solitude and fish can be found on less than these perfect lies. Fish don't like crowds either, and perfect water lies often get pressured so much that fish move on. This is especially true for sea-runs, trout feeding on hatches tend to congregate where there are easy pick ens, but that doesn't mean a well placed fly won't coax a strike on sup-prime water. In fact many times these fish are less selective, in regards to fly selection and presentation. Also try fishing nearby less famous streams, creeks, tributaries etc. The same conditions that exist on that world famous stretch are also likely to be going on nearby, especially on the tributaries. You might have to work a little harder for access but the pay-off is less crowds.
Water conditions and weather: Again picking less than ideal will result in more solitude. If you are waiting for the water to drop from a recent storm, going a day or two before water ebbs to that level will result in more water to yourself. Slightly off color water often result in some of the best fishing, as perfect visibility can make the fish more wary. Beautiful spring afternoons are likely to bring out throngs of cabin fevered fisherman, and are best avoided if you are trying to avoid crowds. However afternoons on weekdays are less pressured than weekends.
Time of Day: Many fishing runs and hatches have times of day when fishing is supposedly the best. Many steelhead runs I know are fished heavily from sun up til mid-morning, and others are fished at sun down. As a general rule cold weather runs are fished more in the morning and warm weather runs are fished more in the evening. Learn the ways of the particular runs and fish the opposite. Fish do tend to be most active at these times, but especially on cloudy days fishing can be steady all day long, only the crowds change. Like wise on hatches, true many have peaks during the day. But the fringes of these times can provide excellent fishing with emergers and/or spinners. Some of the most selective fish rarely hit adult duns anyway, although there are often spectacular splashes during the prime of the hatch, I suspect just as much feeding if not more often goes on, before or after the fireworks of the hatch. As stated previously some of these strategies come with trade offs, usually being fewer fish. But in those fewer fish could be the one you remember for a lifetime. Even if that fish isn't caught, the solitude will allow you to fish at your pace, and to fish the water you want with worrying about crowding the fly fisherman down stream.