Hey guys, I've updated this for season 3. Let the haters say what they will on an AD Carry teemo, but this build works frequently for me, and I always have fun playing it. Be sure to read the section on countering and being countered. Do not use Teemo in a situation where you'll almost assuredly lose.
Purchase the Cottontail Teemo skin for the ultimate cute smackdown.

He is a great champion for map control, ambush, and he's fantastic in teamfights. You just have to know what you're doing.

Edit: To answer some questions up front, I don't do AP because:
1. The damage ratio to his poison shot's isn't 1:1, it's been nerfed
2. I don't want to rely on my q and shrooms for damage so much as scouting and support.
3. AD items like Frozen Mallet and lifesteal suite my playstyle, and the style of the build.

Play it before you knock it. You shouldn't find a game without 10-15 kills if you're playing it correctly.

Runes for Teemo are a toss-up. I play these, because they are what I have. Flat damage, or attack speed may be solid alternatives.

These are solid, rounded stats for an AD hero, because now you can focus on building your damage and movespeed without having to worry about Armor Penetration and defense.
Again this is what I use, I'm not saying it's the only option.

This is how I build my AD champ mastery tree for season 3. A few swaps here and there might suite your play better. Test it and see!

I always begin with boots and potions, then I farm for either a BF Sword, or greaves and a Doran's Blade next.

Late game, you will see yourself controlling enemy carries if you can get yourself a Frozen Mallet and Infinity Edge by mid game.

A lot of people recommend Malady on Teemo. I have used it several times, and to be honest, it's a waste of gold that you could be spending on heavier damage.

With Teemo, movement speed is my key attribute. I start with Boots and 3 HP Potions. Unless I have an aggressive support with heavy cc, I stay behind the minion wall and keep up my farm. Teemo has great harassment because of poison, so occasionally jumping ahead to put a few darts into an opponent makes fights and ganks easy for a Teemo lane.

I always max Teemo's poison first, and put a level in the Blinding Dart for utility. I don't level the Blinding Dart up again until both Poison Darts and Move Quick are maxed out. AD Teemo doesn't rely on his Blinding Dart as a damage source, so much as a great disable for enemies, or a nice long ranged poke for an extra hit in harassment. Those two or three hits can mean the difference between a won or lost teamfight, so it's important to gauge when the blind will be the most efficient. Note that the blind won't stop enhanced attacks like Xin Zhao's or Nasus' Q!

If your support doesn't already love you by level 6, he should shortly after. Ward your bushes and any back lanes that opponents could hit you from, and begin to branch out to Dragon/Baron, your jungle, and mid. Your support should only need to use wards for heavy traffic points thanks to shrooms.

If teemo is an AD Carry, he probably shouldn't be split pushing, since his team will rely on him for team fight damage, but if your team is able to hold fights without you, or if you're a top Teemo, split pushing and backdooring turrets is a great plan.
Use shrooms to alert you to any enemies flanking you, and be sure to actually watch them.

Teemo is great for gank. With your Frozen Mallet providing a slow to the enemy, movespeed items in your favor, and hopefully by now some of the heavier damage items on the list, you are very hard to escape. AD Teemo puts out a HUGE amount of damage. If you play aggressively in 1v1, or ganks, and utilize your Q ability, you will come out on top an overwhelming amount of the time.

During teamfights, be sure to avoid cc, and to kite as much as possible. Don't be shy with shooting the nearest target if you can't catch the enemy carry, but when a more prime target presents itself, always switch.

Don't ever first pick Teemo. That's just begging for it. Teemo is a strong carry, but he has some definite strengths and weaknesses.

Teemo is particularly strong versus champions that rely on basic attacks and line based skillshots for damage, and any melee champion without a gap close. This is why I will use him to counter champions like:
Varus: Dodge his wind-up pokes easily with your speed, and then charge him. Varus can't do anything to you if you can dodge his skillshots and land those blinds.
Ezreal: If you can dodge the skillshots, Ezreal does very little damage when blinded. Just keep in mind that his jump will deal damage to you, and that you'll really need to be paying attention for his spam. He shouldn't be able to withstand many of your hits, so just pepper him if he's on top of you. Kiting is useless at that point unless you've got preemtive shrooms to lead him through.
Vayne/Ashe/Draven: Perhapse not a counter, because she's got a great cc, and hefty hits to a little guy like Teemo, but a prime example of a champ who relies mostly on basic attacks for damage.
KogMaw: Kogmaw isn't necessarily countered by Teemo, but flash in on him, pop ignite and start whacking him. He goes down so fast, you shouldn't need to worry. (obviously don't do this if he's got a cc based support like Taric.) If you must hang back, just utilize your harass, and farm up. He's really mana hungry if he wants to do any early game fighting.
Olaf: Teemo is a great Olaf counter, simply dodge axes, and kite while you attack. Olaf relies way too much on his axe, and if you don't let him get close, he'll either just leave you alone, or keep trying and die. If he ultimates, just run and wait for it to run out.
I also main Olaf, and can kill a Teemo. If you aren't smart or fast enough to dodge the axes, you're not a counter.
Garen/Singed/Warwick/Darius/Shen: Similar idea. Just keep your distance. If you see their aggressive chase abilities go down, either run or drop a shroom where you stand. Anticipate Warwick's ult, Shen's dash, Darius' grab, and don't get caught somewhere where it will get him a kill. If they can't catch you, they can't do anything, and harass heavily to counter any hp regen. Keep them low and nervous.
Tryndamere: Tryndamere is formidable to any champ, but if you can lay down some damage while he's blinded, anticipate his slow when you turn around (by turning around, then turning back to him immediately for a shot, and then redoubling back), and by utilizing your speed, damage over time, and ignite during his ultimate, Teemo will crush Tryndamere. He will be more formidable late game, so don't get overconfident.

Teemo is weak versus ranged stuns, and heavy nuking. I have won against, but wouldn't count on wins in a 1v1 versus champs like:
Corki/Graves/Tristana/Miss Fortune: These guys do great burst damage, and have some abilities that make it particularly hard to avoid them. I'd recommend choosing someone else to face the nuke champs.
Sivir: Sivir's spell shield soaks a shroom hit, or your blind, and feeds her mana. A good Sivir will just turn it on and hit obviously placed shrooms to keep a heavy push on you. Her bouncing attacks can't be stopped by a blind, and she's very tough to catch/escape with her ult.
Caitlin: She's such a pain without some ranged cc. You're not gonna catch her with that net, and her ultimate is a real pain, since Teemo doesn't always leave a kill with a ton of left over hp. Her enhanced attack isn't effected by blind.
Annie/Veigar/Kassadin/KhaZix/Leblanc/Swain/Talon/Kat/Akali/Shaco/Brand: Watch for these guys in team fights. Hang back away from the group enough to let them blow their stuns and hopefully their heavy nuke cooldowns. Those hefty target nukes are gonna rock your world. A Banshee's Veil would certainly help, but that's a lot of money mid game that an ad carry should be investing into damage.
Jax/Renekton/Irelia/Pantheon/Xin/Wukong/Nocturne: These are all top lanes or jungles that effectively counter Teemo. Don't pick Teemo if you see these picks locked in, and switch a lane with someone if they counter pick you. Hang back and wait for ganks, these guys have great gap closes, high hp, stuns, and heavy damage once they're on top of you.