There are so many variables, but I would say that in general if it is your butt that hurts you are doing it right. When I get on my bike for a long ride after not having done so, my "sit bones" almost feel bruised, however, the soft tissue I really want to protect is better off for it.
Other things:
A saddle too high or too wide can pull you forward onto the nose of the saddle, which can be very uncomfortable.
Poor posture can affect what hurts too--just try it out. Slouch forward while riding your bike (for comparison), then exaggerate great posture by rotating your hips forward and pushing your chest out. See if that eases the pressure.
The more you ride the harder saddle you will probably want. It's kind of like a couch--when you plop down at first on a fluffy one you think it feels great. By the end of the super bowl it is miserable...eventually you will want support from your bike seat, not cushion.
And while "going to the store to buy a solution" might not be mustachian, you might consider visiting your local bike shop. If you can, ride your bike there. The good shops will take care of you--have a seat demo program, a return policy, etc., and should suggest some of the things that we already have. If they don't, you can always leave.