Across most of Wyoming, nobody is going to stop and search you in any case. But the cities are turning more "liberal" all the time. I'd stay out of Cheyenne, Laramie and Jackson Hole if I were you. Cody is not always gun friendly either. But you are probably not going to have a problem as long as you don't do anything stupid.
I live in Laramie and frequently go to Cheyenne and I OC when weather permits. Yes Laramie is a college town but the liberal attitude has not infected either the city police or sheriffs dept, I have frequently encountered officers from both departments without problem and had pleasant about firearms several times.
Cheyenne is the state capital, but is more like a small town; hell there are only ~ 550,000 people in the 10th largest state and least populous of the contiguous 48 states. There is NO problem OCing in Cheyenne, I do it frequently and never draw a second look. I was in Lowe's
the other day and there was a problem finding an online order, the manager was on the computer, while waiting on the computer he looked up and asked "What-cha carrying" I explained the Para P-14 and he just smiles and said "Sweet. I like it when you guys come in, keeps the bad guys guessing".
I honestly can't think of a place in Wyoming that you would have trouble OCing except buildings in Yellowstone occupied by NPS personnel, I have OCed in the park several times with no problem.