When trying to get started with flash photography, there are a lot of new options, features and techniques that a photographer gets thrown in to. When starting on a budget, what features will give a flash the most bang for the buck for people just starting out in flash photography that don't have a lot of money to spend?
First and foremost, sufficient flash power is necessary. Flash power is measured in guide numbers. With guide numbers higher is more powerful. At a given ISO and focal length, the guide number is the aperture times the distance to the subject. For example, a guide number of 100 should be able to expose a subject at f/4 that is 25 feet away. It's also important to make sure that you compare apples to oranges with guide numbers that are using similar ISO and focal length numbers.
You also want to look for a flash that has a tilt (and preferably swivel) head. It's very important to be able to send the flash where you need it. Many techniques like bumping flashes off ceilings and walls will give a much more professional look, but also require the ability to send the flash off angle. This is a very valuable feature for a flash to have.
Another consideration that is probably a little less critical (and can be adjusted for) is flash dispersion. How well does the flash spread out the light? If the light is too concentrated, then photos up close will have portions of the image underexposed and other parts overexposed. You can fix this with flash diffusers, but they will also cost you some flash power (typically anywhere from 1/3 stop to 2 stops of power.
You will also want to consider what kind of metering to use if any. If you photograph mostly scenes where you can redo shots and carefully setup your lighting, then metering may be something you can skimp on in favor of other features, but you'll have to either meter your flash with an external meter or work it by hand and some trial and error.
On the other hand, if you are going to be shooting things that you only get one chance on or can't be taking the time to experiment with manual adjustment, then at-least some form of metering is a must. You can get a flash with an integrated meter that you can manually tell it what settings you are shooting on with the camera and do a test flash and it will adjust the flash appropriately for you. The main draw back is it requires a flash exposure prior to taking the shot since the camera and the flash still aren't talking to each other (other than to say the shutter was pressed).
In most cases, just about any hotshoe flash should recognize the shutter release signal and if external metering or manual settings are used, just about any hotshoe flash should work on just about any camera since the shutter release signal is pretty universal. The main side effect of using off-brand flashes though is that TTL typically won't work.
TTL stands for Through The Lens metering. In a TTL setup, the process is actually pretty similar to an externally metering flash, but it happens MUCH faster and uses the actual sensor within the camera for metering (so that filters, optics, etc are taken into account.) When you take a shot in TTL mode, the camera tells the flash all the settings being used for you, it then fires off a pre-flash, checks the exposure and adjusts accordingly for the actual exposure, the actual exposure then automatically occurs with all the factors taken into consideration. The entire process happens so fast it normally appears to be a single flash. It is a very nice feature to have, but also one that can be given up in a pinch in favor of external metering, particularly if you don't make much use of filters that reduce light captured by the camera, but if you can afford it, it is very nice to have. Also, as mentioned before, in most cases, TTL rules out other brands of flash (some third parties have reverse engineered it) since each camera manufacturer uses their own proprietary signals for TTL.
Moving more into the realm of nice to haves, having a sync cord hookup is useful for being able to reuse a cheap flash down the road once you start getting more into flash photography and want to upgrade. One of the great things about flash photography is that it is very common to use off camera flashes. If your current flash today can be your off camera secondary flash tomorrow, it can save your investment from finding it's way on the the trash heap quite so soon. If you are on a really strict budget though and expect to have more funds available in the future (say a student) then it may not be worth investing in this feature over having a higher guide number or a better level of metering.
One final thought is that you also want to consider the cycle time for the flash. The electronics in all flashes are not created equal. If you plan on doing mostly studio work, then a cycle time may be less of an issue, but for events or any kind of higher speed shooting, having to wait 5 or 6 seconds for a full power flash can be a lifetime. This is another one that is really dependant on how you expect to be using the flash.
Similarly, the life expectancy of a flash is important to consider if you are going to use it alot. How many flashes can it take before needing new batteries and how many exposures is it rated for before the flash starts losing power, how about before it is dead? Flashes start to lose power relatively quickly. Even a high end flash like the Canon Speedlite 600EX-RT will start becoming less powerful after just a few thousand flashes. Now, that doesn't mean it turns into a pumpkin, but it does mean that the guide number slowly starts slipping down. Cheaper flashes often equals cheaper flash bulbs and the fade off can start after 1000 flashes or fewer. For the occasional flash photographer, this isn't really an issue, but if you plan to work with it a lot, keep in mind that rapid thermal shock cycles are the hardest on a flash (so if you can let the flash cool down between shots, it will thank you in the long run.)
The most important item is whether or not it has TTL (iTTL, CLS, etc) and if you require it.
Manual flashes are much cheaper than TTL capable flashes. They are recommended by David Hobby, the Strobist. See http://strobist.blogspot.com/2006/03/lighting-101-start-here.html He states that manual control is mandatory for proper flash work, and some branded flashes only work TTL
There are TTL third party flashes. The Strobist discussion group on Flickr has many threads weighing the pros and cons of specific models and brands. http://www.flickr.com/groups/strobist/discuss/
Here are my must have features: