I know that this is not what you want to hear, but there is no way to tell.
Melons thrive in places with a hot and dry summer, like Turkey. But they will also grow and bear fruit in climates which are less than optimal. Among melon growers, a rainy summer is always considered bad for the melon, but I don't know if this is because of the excess water, the reduced sunlight under a cloudy sky, or both. Anyway, melons grown in the right place in a bad summer, or melons grown in the wrong place, will not produce sugars. The fruit flesh is firmer and more watery than that of a sun-ripened melon, with a slight cucumberlike quality. The individual cells are small and don't separate easily, so you couldn't mash it well if you wanted. It is a bit like the difference between mealy and waxy potatoes.
But you can't recognize the difference from outside. The rind of both kind of melon, dry/hot ripened and wet/shade-ripened, looks the same. The only sure way is to taste the melon.
A few things can improve your chances of finding a good melon, but it is still a hit and miss.
Don't buy at supermarkets. Supermarkets sell large amounts of efficiently produced and cheap food. Supermarket produce is optimized for cheap production, high transportability and good looks, not taste. Whatever they do for it, it really reduces the quality of sun-dependent plants like tomatoes, melons and plums. Produce on the market doesn't come from a farm around the corner, but it is frequently much better quality - I suspect that it is just a matter of price differentiation and large farmers who are willing to invest in quality processes see them as the place where they can get a higher price. Small ethnic groceries also carry good quality produce, here it is mostly the Turkish ones which have it.
The knocking GdD described is used to identify ripe melons, and usually used on the field to decide which ones to harvest. I would like to think that the store isn't selling underripe melons (as I mentioned, the sweetless ones are not unripe, but grown under the wrong conditions), but if you suspect it might be the case, try it. A ripe melon sounds hollow with lots of resonance, an unripe one sounds muffled.
Smell the melon. Melons produce not only sugar but also aromatic compounds when they ripen properly. If you can't smell anything, there is a high probability that the melon is tasteless. If you get some aroma, then it could be good or bad. If you are in the same room with perfectly ripened freshly harvested melons, you can tell it by the smell without bothering to go close to them, but I have never experienced it in a store.
If the store has a cut melon on display, you can try to inspect the appearance of the cut surface. It is a bit hard to recognize it if you don't know what you are looking for, but it is generally a mealy appearance. In the best melons, especially watermelons, the cells can be easily seen with the unaugmented eye, and the flesh will have areas with dryish, bursting cells with lighter walls and cracks in them. It is again seldom seen in grocery stores or supermarkets, but still, a wet, firm, uniform flesh is a bad sign. Don't pay attention to the flesh color. It is dependent on the cultivar and unrelated to sweetness. Pale greenish melons can be juicy and sweet, deep orange ones can taste like cardboard.
I can't recommend a variety which is better than the others. All farmed varieties of melon have been selected for years for good taste. The current large-scale farmers may have created worse tasting strains of them by selecting for durability and appearance, but these are not labelled as separate varieties. So, you can have a good and tasty honeydew, cantaloupe, etc. All of them are good when grown and harvested in the right conditions, your problem is not the variety but the production process.
I hope this helps you a bit. I am afraid that even with all I know about melons (my grandparents used to have a field for private consumption), I am hard pressed to find good ones to buy. But if my geography imagination is correct, Australia has a better climate for melons than does Central Europe, so maybe you will have luck finding good local melons.