It starts with electric vs acoustic; which one do you want to play? If you want to play acoustic the following will still apply, but the guitar recommendations will be invalid.
The most important thing is comfort. Don't worry too much what a sales guy tells you about a guitar's electronics (e.g. pickups) -- that's not going to matter just yet. Try out a bunch of guitars and pay special attention to how the neck feels to you.
Many non-guitar-geek folks take this for granted, but all guitar necks feel different. Some are big and fat, some are thin, and others are shaped like a V. Most are rounded in the back.
If your hand is not comfortable on the guitar, don't buy it no matter how cheap or how cool it looks. At a 100% beginner stage, quitting is a giant possibility and in my opinion pain and discomfort will lead to you not enjoy playing and you'll eventually just quit.
Another related note is how the guitar is set up. A good setup on a guitar is the difference between the string buzz versus the strings being 1/4th inch off the fretboard versus a nice comfortable distance from the frets.
Although almost any guitar can be setup to play pretty good, at some stores (typically giants one like guitar center), the cheaper guitars aren't well maintained at the store or come poorly setup from the factory. Those are a nightmare to play. At a decent store, they should be able to set a guitar up for you. I would highly suggest you to ask for a quick tweak if you find a guitar you like but its strings are a tad too high or buzzy. It should only take a couple minutes and they should do it for free.
The last bit of advice I would give is... buy a tuner. Cheaper guitars can go out of tune pretty easily (especially with new strings). When the guitar goes out of tune, most of what you play will sound crappy and you won't get that "woah, that sounds right" feeling when you strum chords or play even simple licks. So buy a tuner and make sure you're in tune.
Summary:
- Buy a comfortable guitar
- Make sure the setup is decent before you pay them money
- Buy a tuner and stay in tune
- Practice