My father is one of the patent examiners for mattresses. I brought him along the last time I bought a mattress. His recommendation was like ChristianKl's: try different mattresses and see what's comfortable. Cost and comfortableness are not necessarily related. Whether or not you find it comfortable in the store is the best indication of whether you'll find it to be comfortable at home. Pick the cheapest one you find comfortable. With that being said, you might find some more expensive mattresses last longer, though he indicated that most mattresses are designed to wear out around the same time. Also, he's highly skeptical of the value of memory foam and other things you see on TV, so don't think those things are necessarily better.

For what it's worth, he sleeps on a waterbed. I am unsure, but I think the choice might be motivated by my mother's allergies; waterbeds can't absorb allergens by their design.