As you might have noticed, a large percentage of Provo is made up of Mormons, members of The Church of Jesus Christ of Latter-day Saints. In fact, it seems like people generally assume that you are unless you give them a reason to not. For more information about that, the official website for the church is http://lds.org.
As such, you will see LDS churches all over the place. The buildings on BYU campus turn into churches on Sunday as well, as student wards (congregations) meet there. It's really easy to find a ward, you can pretty much go on campus anytime from about 9-1:30 or so and follow people to their ward, about every half an hour. It is a little more tricky to find the ward you are actually supposed to be in. The link to the BYU student wards with locations and meeting times is here.
If you go to http://lds.org you can go to About the Church then to Find a Meetinghouse but that probably is not all the helpful if you're trying to find your specific ward (especially if you're a student, you should go to the other link). Asking your roommates or neighbors is a pretty safe bet.
There are a couple churches of different faiths here though:
St. Mary's Episcopal Church - 50 W 200 N - (801) 373-3090 - http://www.stmarysprovo.org/
Community United Church of Christ - 175 N University Ave - (801) 375-9115
Provo Bible Church - 1449 W 1150 S - (801) 373-8272
Provo Baptist Church - 230 W Center St - (801) 374-2644
Kingdom Hall - Jehovah's Witness - 491 N 1280 W - (801) 374-9015
Rock Church - 244 W 100 S - (801) 655-0054
Seventh-Day Adventist - 255 S 700 E - (801) 374-2978
Rock Canyon Assembly of God Church - 3410 N Canyon Rd or 3214 N University Ave # 617 - (801) 377-0448
St. Mark's Lutheran Church - 464 W 3700 N - (801) 225-5777
Iglesia Biblica Bautista El Faro (Baptist Church) - 817S Freedom Blvd - (801) 372-8102
Haamonga O Kalaisi United Method (Methodist) - 1044 N Geneva Rd - (801) 377-2352
United Penecostal Church - 236 N University Ave - (801) 374-1343
There may be a mosque meeting on Fridays on BYU Campus...
In Orem:
St. Francis Catholic Church - 65 E 500 N - (801) 221-0750
