Was out that way in August. Didn't end up with time to fish there but did do some research. If you google 'Utah fly fishing' or 'Provo River' you'll find a lot of information.
Steve:
The Upper Provo is mostly private water. The Middle has tons of access from River Rd off of Rt 40 to the right. If you go left at the light and make a quick right this road runs right up to the Jordanelle Res. The Lower Provo has quite a few easy access points, from just below Deer Creek Res down to where Sundance Ski area's access road is. If you plan on going there shoot me a PM or E-mail. I fish there 4 to 6 weeks a year.
Was actually out there 2 weeks ago my family has a place in park city. Fishing was good alot of access points as everyone said, and a alot of private water in the upper. Shoot me a PM if your going I'm due for one more trip there soon, and know a few of the private land property owners.