No romaji. Romaji hurts your pronunciation and is a crutch. Get something with furigana, or even better, hiragana in parentheses.
Lots of example sentences. Context is invaluable in learning new words.
Electronic is better. It's faster and can be used mid conversation much more easily. Plus you can write in unknown characters with a stylus. Plus if you get a good one you might never need to replace it.
Once you are at a high enough level you will want to make use of a 国語辞典 (Japanese dictionary in Japanese). They are often more thorough, and some stuff is just hard to explain in English.
There are a couple things to keep in mind when looking for a dictionary:
How easy is it to find what I am looking for? A given dictionary might prove to cover every single word in the Japanese language, but if you can't find what you are looking for then you will think it is just a waste of money. Your best bet here is to look for ones that are used by other students and try and examine it yourself. Also, remember that you will need to get used to Japanese before you feel really comfortable using the dictionary unless you limit yourself to the romanized ones (i.e. Random House Japanese-English English-Japanese Dictionary).
How long can I use the dictionary for? If you are planning sticking with Japanese and learning the language then investing in a more expensive dictionary might prove useful (i.e. The Kodansha Kanji Learner's Dictionary); however, if you just need a quick reference for a trip then you don't need an extensive one.
How will the dictionary help me learn? Beyond the obvious use of the dictionary to look-up new works that you are unfamiliar with, some might prove better than others for learning the words once you look them up. Having the furigana (i.e. Kodansha's Furigana Japanese Dictionary) on hand with the kanji will help students in that they now see the words in question in two different scripts in addition to the the definition that they are looking for.
Beyond that, a dictionary will come down to a bit of personal preference, while the ones previously mentioned could cover most of the basis and provide a wide coverage of the language, you may eventually graduate to the point where a proper Japanese language dictionary is required or you may desire something a bit more exotic such as a loan-words only dictionary.
An online dictionary is much more useful than a paper one. Online dictionaries can be updated with new words and meanings and searched more quickly. There are a few free online Japanese<->English dictionaries, but the best one (in my opinion) is http://jisho.org/.