Most important of all - they should smell. A lot. Any fruit that you have to put right up to your nose and sniff hard in order to get the frangrance of is under-ripe, overpackaged, sprayed and refrigerated cack.
With watermelons it is considered a mark of quality if the stub of the stem is still attached - I'm not sure if that's a mark of freshness (the stub will dry off in time) or just a superstition, though.