The best learner dictionary by far is the one by Josef Fronek. It not only has the gender but also references all the declension models making it easy to find and generate any forms for both nouns and verbs. It is the most uptodate and modern bilingual dictionary.
Of the pocket dictionaries, as far as I know, only Nina Trnka's dictionary has gender information but it is quite old and has many other imperfections.
Of the online dictionaries, DICT.cc is one of the few that references gender.
As to the why, it is very easy. Most Czech-English dictionaries are made for native speakers of Czech who do not need the gender information. Therefore it is not included. In fact, they would probably find it a bit puzzling.
And since most dictionaries are not made from scratch but rather by building on previous efforts, if the templates do not include gender information, their successors won't either.
If you look at the three dictionaries above, they were made with non-native learners of Czech in mind (if not as primary audience - except perhaps Trnka). The Lonely Planet Phrasebook which is aimed at non-native speakers contains gender information but it's not really a dictionary - although it could be used that way with the index.
Unfortunately, there is no reliable way to predict gender from the form of the noun. Here are some of the key rules:
There are some which are almost exception proof:
Nouns ending in b, g, k, h, ch, d, r, p, n, m, l are always masculine
Nouns ending in a are almost always feminine (with a few exceptions that are masculine)
Nouns ending in o are always neuter
Nouns ending in í are almost always neuter (with a few feminines)
These will at least help you exclude a gender:
The largest Czech monolingual dictionaries do report gender but they are a bit unwieldy for the learner. Some of them are now available to search online. The best for look up of gender is here with the added advantage of being able to look up any form of the word and seeing all the other possible forms. There are no English equivalents in this dictionary.