Kyle,
I'm planning a similar trip. I made a post about this a month back, and there was some good info there. It's 3 posts down in the Western United States area of the forum titled "Planning a trip to Montana..." From what everyone has told me, post-runoff is the best time to go up there. This means any time after mid-June. If it is your first trip, you might want to pick out two or three rivers and focus on them. My plan is to drive up to Bozeman and set up camp there (or around there). From there you have VERY easy access to the Big Horn, Yellowstone, Gallatin, and Madison Rivers. Take your pick, its Montana, they're all good.
If you're in search of some big boys then I suggest you take a look at the Missouri River. It's a good distance away from Bozeman though, and you can pretty much forget it if you don't have a boat. The tailwater is DEEP.