First, there are all kinds of trout fishing opportunities. I'd venture to guess that for the visiting angler, Montana offers MORE trout fishing than any other state, and in some ways that includes Alaska. Wanta catch wild browns and rainbows? They are everywhere. Want to go for native cutthroat? Two or three different subspecies. Bull trout? Yep, even if you can't keep them and aren't supposed to specifically target them. Brook trout? Yep. Even grayling. And lake trout, though I question why anybody would want to actually fish for lake trout when they have all those other trout to pursue. Want to fish still water? Plenty of small lakes and big reservoirs with trout. Big western rivers? All over the state. Little creeks where the trout haven't seen an artificial fly? Uh-huh.
And best of all, Montana has the most enlightened stream access laws in the country. Basically, if you can find a place to get on it without having to use private property without permission, you can fish it for as far upstream or downstream as you can reach, no matter who owns the land around it...with a few exceptions. But that's what makes Montana different. Wyoming, Idaho, Colorado...all have a lot of water that is strictly private and off limits. Not Montana.
Yep, it can get crowded at times and in places, but having all that water to fish really does spread out the pressure immensely. You'll probably see fewer anglers on a given day in Montana, on average, than you will on public water in Colorado.
I don't much care for lake fishing, so I almost never do it in Montana and don't know that much about it. As for streams...I certainly haven't fished them all. I wouldn't be able to fish them all if I was 18 years old and had my whole life ahead of me and nothing else to do. Here are the ones I have fished and/or at least know people who have and therefore know something about:
Bozeman-Livingston area (my stomping grounds)
Yellowstone River--my "home waters" in Montana. Leaving aside the river within Yellowstone Park, which is mostly in Wyoming anyway, I've fished it from Gardiner to Big Timber. That's something like a hundred miles of prime trout water. Holds browns, rainbows, and native Yellowstone cutthroats. Big, fast, powerful river, but still has wading opportunities. Gets fishable at about 10,000 cubic feet per second some years, drops to minimums of 1500 cfs some years. Has some great hatches. But it can be one of the tougher rivers to have real success on. A good day on the Yellowstone will net you a dozen or so trout, and most will be 12-15 inchers. Under the right circumstances you can catch multiple 20-23 inchers in a day, but the right circumstances are rare. And it gets extremely crowded with rafts and driftboats full of rod waving anglers in July and August. You can still catch fish even if you're 10th in line to fish that bank, but the fish get sophisticated about avoiding patterns that worked a couple days before.
Gallatin River--known for smallish fish. It's a much smaller river than the Yellowstone, and far different for much of its length, flowing through a deep, narrow canyon with just the river and a highway taking up most of the canyon bottom. A lot of it is fast, pocket water with big boulders. Once it emerges onto the big, flat valley around Bozeman it changes to a river much like a far smaller version of the Yellowstone, with riffles, pools, and a bottom mostly covered with rocks the size of your head. I haven't fished it all that much because there are rivers I like better, but I've had a few good days of dry fly fishing on the lower portions. It's pretty much all wading water. Floating it is problematical in the canyon and in places illegal down by Bozeman. Most of the trout you catch will be under 15 inches.
Madison River--one of the most famous of Montana's rivers, with good reason. Basically, most of the Madison is just one big riffle; wide, shallow, studded with rocks and clumps of submerged aquatic vegetation. It gets extremely crowded in the summer between West Yellowstone and Ennis (with anglers) and just as crowded on the lower river below Beartrap Canyon, but with party floaters, since the lower river comes off the top of Ennis Lake and is warm enough to be comfortable for swimming--and warm enough to be stressful for trout. Still, I love fishing the lower river in the spring and fall. The Bozeman area guides always take their clients on the lower Madison when the Yellowstone gets blown out, and some of the Livingston guides do, too. Lots of browns, maybe more of them than rainbows, and they can get big.
Boulder River--this is the one near Big Timber, not the other Boulder River in Montana, which I've never fished. It's wading water, easy access in most places, not easy wading in many stretches because it's aptly named--boulders the size of basketballs to the size of a Volkswagen everywhere. Can be excellent fishing. Some brave guides float it in the spring when it's a little high. At that point, the Yellowstone will probably be blown out, but the Boulder stays clear (and cold) even when it gets pretty high. As my guide buddy said, though, you have to know how to make the right moves on the Boulder in high water. Plenty of resident rainbows and browns in the 12-18 inch range.
Shields River--a little stream, wading water except in the high water periods, mediocre fishing but it's close and easy to wade most times. Gets too warm and stresses the trout in mid-summer. Mostly smaller fish.
Stillwater River--a lesser known float stream, and if the Boulder is aptly named, the Stillwater is the most IN-aptly named river on earth, because there is just no still water on the Stillwater. Most of it is a boulder garden, punctuated with a few ledges that form scary rapids in higher water levels. But the fishing can be terrific. Upper reaches in the mountains are beautiful and interesting wading water. Lots of 14-18 inch trout.
Small creeks that are tributaries of these rivers--get up in the mountains on National Forest ground, much of it Wilderness Areas, and if you are in shape and don't mind worrying about grizzly bears, you can find cutthroats that have probably never seen another angler. Even when the creeks get closer to the rivers (but before they all get diverted for agriculture) you can find good fishing for native cuts. Few of them will be over 12 inches, but it's great fun.
Some farther away rivers I've fished
Bighorn River--one of Montana's most famous and popular rivers, it's a tailwater fishery. Fairly big river, clear, not too fast, used to have the highest concentration of browns and rainbows of any river in Montana but it's not quite as good as it once was. You'll see trout rising everywhere a lot of days, and you probably won't figure out how to catch them, but other days you can fish small nymphs and catch 14-17 inchers all day long. And then there are those days when they all get stupid and you catch them on dries or even streamers.
Big Hole River--suffers some years from too much water being taken out for agriculture, but on good years it can be terrific fishing for BIG browns, with rainbows and even grayling on upper sections. My best streamer fishing day EVER ANYWHERE was on the Big Hole in April.
Missouri River--in the Craig area is where I've fished it a number of times. It gets tough in mid-summer mostly because of too much dislodged, drifting aquatic vegetation; the trout are still there and willing but you can't make a cast without fouling your hook. But most of the year, as a tailwater fishery, it's very fishable and very, very good, with 14-20 inch trout seemingly everywhere. For a combination of numbers and average size, it may be the best stretch of river in Montana. Big water but not too fast, and easy floating with some wading opportunities.
Smith River--I haven't fished this one but my guide friends have. It's a permit river--you have to apply at the first of the year for a permit to float it during a specific time period. It's kinda like the Montana version of the Jacks Fork, smaller water, narrow canyon, wilderness character. When it's best fishing it's almost too low to float, and if you try to get a permit for when it should be good fishing, you might end up not being able to float it because it's too low. But it's absolutely beautiful and the fishing can be great if you hit it right.
Musselshell River--the parts that have trout are pretty small, but it's a little known stream compared to most. Access is problematical, though.
Obviously there are a bunch more rivers in Montana...Blackfoot, Clarks Fork, Flathead, Ruby, Bitterroot, Beaverhead, the other Boulder, Jefferson, Judith, Kootenai...but these are the ones I know well enough to mention.
When to go--first of all, when probably NOT to go...it's COLD in Montana in the winter and the winter lasts a long time. Unless you live here, you probably won't get lucky enough to find fishing from mid-November to mid-March. And the other period you probably won't want to plan your vacation for is in May and June, because that's snowmelt time and all but the tailwater rivers will probably be flooded and unfishable. If it's a cold spring, you might still have fishable rivers up into May, and if it's been a dry winter they might get fishable again by mid-June, but don't depend upon it. You can still find fishable water during the snowmelt on the tailwater rivers like the Bighorn and Missouri, but your options are definitely more limited.
Which leaves three basic periods. First is in March and April. This is my favorite time to be out here for the fishing. The trout have just come through a long, hard winter and are hungry, there are some decent hatches and one or two terrific ones, and there aren't as many tourists out here fishing. The "Mother's Day" caddis hatch on the Yellowstone, if the stars align, is unbelievable both for numbers of bugs and for dumb trout the first couple days of the hatch. After that they get satiated with caddis and the fishing gets tough even if the bugs are still there. Weather in March and April can be surprisingly pleasant or unpleasantly cold and snowy, and can be both in the same week. But if you don't mind a good possibility of bad weather, it's a great time to fish. If it's a warm spring, some rivers can get blown out in mid-April, or get temporarily muddy even before then, but usually even in a warm spring you can find water to fish up through April.
Second, July and August. By far the most crowded time. If you come in late June, you can hope for the salmon fly hatch, which usually happens then but often happens before the rivers get down enough from the spring high water. The salmon fly hatch on the upper Madison will probably see the greatest concentration of anglers anywhere in the state at any time, because the Madison tends to get fishable a lot earlier than most other rivers and so the salmon flies are hatching in fishable water levels. Personally, I've fished the Madison then but my strategy is to go where the hatch ISN'T happening (it doesn't happen over the whole river at the same time), because then I'll probably have the river almost to myself. After then, by late July the hopper fishing will start happening. There are ALWAYS lots of hoppers, but not always good hopper fishing, from then all the way into September. Some years it can be great, other years the fish just don't seem to want to eat hoppers. Weird. The major rivers will be full of guides with clients in driftboats and rafts, but you can avoid some of the crowd by putting in a daybreak--the guides usually don't get on the river until 8 AM or so.
September and October. Like the spring period, the weather can be great one day and horrible the next. We usually get the first snowfall in southern Montana in early September, but usually a couple days later it will be 70 degrees and the snow will be gone. The rivers are low and clear and the fish have had all summer to get smart, so it ain't easy fishing. But the scenery in the fall in Montana makes everything worth it. In a warm fall the hopper fishing might last til October. You get good hatches of lots of flies, and sometimes the trout actually eat them with abandon. You won't see all that many anglers. Fall can be especially good on the tailwater rivers because it's been tough during the summer and now the anglers are going to all the other fishable rivers and neglecting the tailwaters a bit.
For the visiting angler like Fshndoug with a driftboat--all the popular larger rivers have shuttle services--just call them and arrange a shuttle on whichever stretch you want to go. Carry spare keys for your vehicle, and all you have to do is put in, leave your vehicle at the put-in with keys somewhere you've arranged with the shuttle service to find (most everybody just puts them inside the gas cap unless it's a locking gas cap), and sometime during the day a driver will be let off to take your vehicle to the take-out. The services have it all down to a science. You can get shuttles online at shuttlequest.com.
Scenery and stuff for the family to do
Of the rivers I've fished, the Yellowstone in Paradise Valley upstream from Livingston, and the upper portions of the Madison are both spectacular, with wide open vistas to high mountains. The Gallatin canyon is beautiful though a little closed in. Scenery on the Missouri and Bighorn is so-so. Big Hole is very pretty in the upper portions. Stillwater in the floatable sections is more dry-land lower hills and agricultural land, as is the Yellowstone below Livingston, though the Absarokas and Crazy Mountain range is usually in view. Lower Madison is pretty, not spectacular. If you stay in the Livingston area you're an hour from Yellowstone Park with all it has to offer. Lots of stuff to do in and around Bozeman. If it's open (it can be closed from October into June), the Beartooth Highway is one of the most spectacular drives in the country, and the highway from Ennis to West Yellowstone is nothing to sneeze at, either...including Quake Lake and the visitor's center explaining the 1959 earthquake that caused the landslide that created Quake Lake by damming the Madison.
But the Livingston/Bozeman area is just one place to base your operations. The Missoula area is probably just as good, though I haven't spent time there. Ennis is terrific if you want to hit the Madison.