If I am going to start playing Magic The Gathering, what set should I start with?
Unlesss you're playing in some sort of tournament, It doesn't matter what cards you use.  

The most popular tournament format is Standard, and the legal cards for that are all the cards from the past 5 to 7 sets.(4 sets rotate out every October)

Standard legal sets include:  Innistrad, Dark Ascention, Avacyn Restored, M13, Return to Ravnica, and Gatecrash.

Generally your local store will be selling these standard-legal sets.



Other notable tournament formats include 

Modern: which is cards printed in a major set since 8th edition.

Legacy: which has no time limit on cards, but there is a list of banned cards

Vintage: which has no time limit, and has a restricted list(you can only use 1 of the card).  the only cards banned in Vintage are cards that deal with Ante and Shaharazad.  

You can learn about other sanctioned formats here.



If you're just looking to play around with each-other casually, than it would be fine, to buy whatever starter decks your store happens to be selling and play them against each-other.

If you're looking to play a little more competitively, the Event decks are designed to be fairly powerful, and able to win a few games at low-level tournaments such as FNM(Friday Night Magic) events.  (your local store might have such events.  you should ask)



your store might also have duel decks.  These are 2 decks designed to be played against each-other.  Not all the cards in these decks are Standard Legal