Off and on magic addict checking in. A few corrections to the generally good stuff mentioned above:
A skilled player on a budget can still rend with the best of them. The problem is that the definition of skilled has changed a bit. Skilled now includes knowing the current batch of cards backwards and forwards, and being a good trader to get what you need. (Yes, you can buy your way in more easily, but a skilled trader will spend much less for the same stuff.)
But forget all that because you’re just playing for fun against each other, not in tournaments, so who cares? It is very possible to spend very little and have a lot of fun with the game.
Unless you have a very good reason to do otherwise, you want EXACTLY a 60 card deck. EXACTLY! Here’s why: The rules of the game say 40-card minimum, but tournament rules say 60-card minumum (for constructed deck). The two tournament rules that just about everyone follows even outside of tournaments are: 60-card minimum, and 4 copy per card limit. If you ever play with anyone else, they will probably expect you to abide by those rules. Given that fact, you want to have the minuimum allowable size to maximize the chances of getting the cards you want. It’s a common newbie mistake to say “oh, I’ll just squeeze in a few more good cards.” Trust me, it doesn’t work. You will get beaten by someone with a more concentrated deck. The only reason to go for a bigger deck is if your deck has a lot of cards that make you draw cards, and you’re worried about running out. (Or if you play with that card that says “you win if you have more than 200 cards in your deck.”) 
blue is more the color of counter magic. Or more generally, meta-magic. It’s a great support color, but doesn’t do a lot on it’s own. Mostly good for:
drawing cards
“bouncing” cards back to their owner’s hand from play
countering spells as they are played
flying creatures
“removal” is generally the domain of red and black. Black spells often just kill stuff directly, and red often damages things enough to kill them. “Bounce” is often as good as removal, but it’s not really removal.
Green is not so much protection oriented, it’s more known for speed. As Tamex said, it’s got lots of mana-producers and under-costed creatures.
There are gold spells that aren’t creatures as well, and some gold cards even have all five colors! (note, even though the card is colored gold, “gold” is not considered a color. A gold card that costs one black and one green is not gold, it’s both black and green.)
2 colors are ideal, at least for starting. If you go to 3, make the third a “splash”. (just a small part of the deck compared to the other two colors.)
Take a look at the back of one of the cards. You see the circle of colors? Notice how each color has two friendly neighbors (Green is between red and white, for example) and two “opposites” (Green’s enemies are black and blue.) You’ll see this crop up a lot in the cards. For example, Green cards with protection from black or blue are much more prevalant than green cards with protection from red or white. Picking two adjoining colors for your deck will (usually) be better/easier than two opposing colors.
A very fun way to play is “drafting.” Take, say half of your 500 cards, shuffle them, and put them in a pile between you. Turn 4 cards face up. Choose the one you like best, and take it. Then let Audrey choose 2, then you get the last one. Turn up another 4 cards and let Audrey choose first. Repeat until out of cards. Then take 15-30 minutes and all the land you want, and build a deck out of what your drafted. (this can be a 40-card deck if you like. draft and “sealed deck” tournaments use 40-card minumums, and no 4 copy limit). Then play the decks against each other for a while, tweak them if you want, then shuffle them back in and draft again.
(There are tons of other ways to draft, this is probably the best for 2 players. You could deal 5 cards and nobody gets the last one. You could choose your cards secretly. You could even draft the worst cards you see, then switch piles before deck-building.)
Another fun thing to do is play with “ante”. Each of you randomly puts one card aside, face up at the begining of the game. (if it’s a land, choose again). Winner takes both cards.
Legomancer’s advice about instants is spot on. The other three biggest newbie mistakes I can think of are:
- Trying to attack someone’s creatures instead of them. Remember. The attacker chooses attackers, then the defenders chooses and assigns blockers. He doesn’t HAVE to block! He can just choose to take a little damage.
- Not understanding the “summoning sickness” rule. Here it is: “In order to attack, or use an ability with the tap symbol in its cost, a creature must be in play under your control continuously from the beginning of your turn.” Note: not to block, not to use an ability that doesn’t require tapping, not your opponent’s turn, your turn. Creatures don’t come into play tapped, they just can’t do certain things right away.
- Not understanding that you can use abilities multiple times per turn. There are many cards that say stuff like: “(red mana symbol): +1/+0”. I don’t know how many time’s I’ve seen someone with 6 red mana available who only “pumps up” the creature once, not realizing you can keep doing it repeatedly.