How often should my troops use Overwatch?

Constantly. You should almost always be in overwatch with several of your team members at the end of a turn.

Ideally, what you want to do is explore a new region of the map or open a new door as the very first half-move of a round. The rest of your round should be focused on dealing with whatever you uncover.

If you encounter a new group of aliens, decide what you're going to do about it. Typically if my first-to-move squad member discovers new aliens, I'll drop everyone back to a defensible position and end the turn with most of them in overwatch. Although there's an accuracy penalty for overwatch, the fact that you'll fire when the enemy is not in cover, coupled with the ability to fight a battle on your terms is very powerful.

If you don't encounter anything at first, use the rest of your units to set up a perimeter of units on overwatch in case you're surprised on the aliens' turn by something flanking you.

There's also a couple of situations where you might be surprised on the enemy turn:

• On "VIP escort" missions, aliens will drop out of nowhere. Being in overwatch means you can take them down before they can cause trouble.
• Floaters can zoom upwards and then descend to another space on the map, although this tends to consume their entire turn.
• There is a glitch (or something odd...) in certain areas I've seen, where Mutons just appear out of nowhere - they don't move into view first, and you don't get a "discovery" cutscene, they just appeared in the middle of my squad ready to fight. If you see one and you can't figure out where he came from, be a bit paranoid for a few turns in case the rest of his buddies show up.
• I've seen glitches where floaters or drones will clip through walls - I've only seen floaters do this once, but drones do this on almost every mission with sectopods/cyberdiscs - they're locked into a formation, and if the big 'bot gets close to a wall, they'll clip straight through it.

In contrast, the very worst thing you can do is sprint into an area you don't control as the last move of a round. Close second is going into a new area when you're low on ammo or not prepared for an ambush. Remember - there is typically no bonus for going fast - play a slow, tactical game unless you absolutely must do otherwise.

After playing a bit more and reading several guides, (including this one here) I've discovered one situation where Overwatch can be bad - the enemy tends to not move if it knows is being overwatched, and if you're in a situation where you need/want the enemy to move (or them staying still and firing would be bad for your squad) it would make more sense to either take a shot, use an ability, retreat, or hunker down instead.

As far as "best classes" for overwatch go, a sniper with squadsight is one of the best, as they can see a very, very long way and deal heavy damage with high accuracy. You can't go into overwatch with a sniper rifle if you've moved during the turn though, (unless you take the relevant perk) so that, coupled with their long range makes them kind of the worst choice for being your advance scout. If I'm going to move a sniper, I'll typically either have him sprint to catch up with the rest of the team, or I'll switch him to his pistol for overwatch mode.

Sniper Perks for maximum overwatch potential:

• Squad Sight - This lets your sniper cover a far larger area with his overwatch - as far as any of your squadmates can see, as long as what they can see is in his line of sight. Very powerful when coupled with Archangel armor, for instance.
• Snap Shot - You can move and go into overwatch on the same turn with your sniper rifle. This would be awesome if you didn't have to give up Squad Sight for it. There's also an additional accuracy hit, which also makes this less appealing. If I was consistently taking 2 snipers into a fight, I might consider this on one, but since I play pretty defensively/methodically, Squad Sight is almost always a better choice for me.
• Damn Good Ground - combined with a grappling hook or the ability to fly to roof areas, this can add to a sniper's ability to dominate the map.
• Gunslinger - This one is halfway decent for a sniper who does a lot of half-moves. Pair this with a laser or plasma pistol and you'll do decent damage even when you can't stay in one spot. If you didn't take Snap Shot, and your sniper can't stay still, this might be a good one to have.
• Opportunist - this boosts your aim on reaction shots, and gives you a chance to critical hit. Both are obviously beneficial for overwatch.

Assault classes can use Run and Gun to sprint and use overwatch, which can be powerful for times when you know you're in a tight spot and need more firepower or coverage. They also can take a perk that allows them to fire a reaction shot when enemies close, regardless of whether or not they're in overwatch. These perks, plus Lightning Reflexes, also make them excellent scouting candidates.

Assault perks for maximum overwatch potential:

• Run & Gun - As mentioned above, dash + overwatch is pretty powerful, especially when the soldier is your forward scout. Being able to establish a safe perimeter for your other, slower soldiers is a good thing.
• Close Combat Specialist - this gives you a reaction shot against any close enemies, without having to be in overwatch at all. Another good one for a forward scout. Be careful, though, as if you're trying to capture an alien, this can sometimes mean you'll kill it instead.

Support classes can take extra movement upgrades, which means they can get into an area that other classes can't reach without sprinting. This makes them good candidates for overwatch. Also, they've got smoke grenades to cover a retreat or provide cover if there just isn't enough.

Support perks for maximum overwatch potential:

• Sprinter - allows you to move 3 more tiles per half-turn. This can make getting into cover without having to use your entire turn easier.
• Covering Fire - Overwatch fires on aliens that shoot as well as move. I don't find this to be as useful, since if they're in cover already, you can just shoot them rather than going into overwatch. If they move to cover and then shoot, you will more than likely hit them while they're moving into cover instead.
• Suppression - Fire on an enemy, reducing its aim, and get an overwatch shot if it moves. This makes a lot of sense for times when you've got a very low chance to hit an alien in cover - you might as well wait for him to come out, and in the meantime give your squad mates a better chance to avoid damage.
• Sentinel - Get 2 shots from overwatch instead of just one. Honestly, I tend to prefer having the additional healing from Savior over this perk. The number of times when you'll want to take two reaction shots is somewhat limited. However, this can be good when paired with Covering Fire, which gives you more situations where you can take an overwatch shot.

The only "average" class for overwatch is the Heavy - they can't move and use their rocket launcher with half a move left, which is kind of a pain. Additionally, their reliance on LMG weapons means accuracy and range tend to be the worst (except for perhaps shotgun-wielding assault troops). They can make up for this with careful choosing of level-up perks, though, so if you intend to make an "overwatch heavy" make sure you pick perks to overcome their shortcomings.

Heavy perks for maximum overwatch potential:

• Bullet Swarm - firing your primary weapon as the first action no longer ends the turn. Might be good for times when you want to shoot, and then enter overwatch. (But if you can see something, why not shoot at it again?) I tend to prefer holo-targeting, for reasons unrelated to overwatch.
• Rapid Reaction - Take a second reaction shot if you're in overwatch and the first shot hits. The only downside to this is that the heavy's LMG tends to be rather inaccurate. Therefore, the chances that you'll hit on the first shot aren't awesome, when you consider the aim penalty the fact that you'll probably be shooting at an enemy from a distance.
• Will to Survive - gives defensive boosts if the heavy is in cover. Since overwatch is best used from cover, this can increase your lifespan if overwatch shots fail to bring a target down.

If it's possible, I will put everybody on overwatch after using the first move of their turn to move.

To play absolutely safest, I will do everybody's first move before putting anybody on overwatch (in case, say, I move soldier 1 to cover, and then soldier 2 finds an alien whose presence makes me decide to do something else with soldier 1's second move, like throw a smoke grenade, run&gun, or fall back, etc.). So, Soldier #1: move, #2: move, #3: move, #4: move, #1 overwatch, #2 overwatch, #3 overwatch, #4 overwatch.

Also, you might wish to use overwatch instead of firing a shot if you have a bad shot due to cover but can make the alien move during the same turn with Flush Shot from another soldier.

Usually the only time I will purposely avoid using overwatch is if I'm trying to keep an alien alive to stun and take captive.

You don't need to be using Overwatch that often. Especially as I got to the later stages of Classic difficulty, I really found that it was overrated.

Aliens typically don't move around that much prior to when you find them. They usually sit in place til spotted, then they will move around. So unless there are aliens that I have seen but can't get a shot at, Overwatch is not a big deal.

Especially at higher levels, even if you see an enemy, they often won't run at you. They will sit under cover, and have VERY high hit percentages even if you are under half cover. Therefore, I'd rather Hunker Down in many cases rather than getting a low percentage reaction shot at best (or better yet, dash from half cover to full cover).

You also probably want to consider the opposition. I will Overwatch much more frequently against Floaters and Chryssalids because they are highly mobile and have low health. In Muton heavy missions I Hunker Down much more frequently since effective reaction shots are so rare.

The exception to all this is Snipers. Snipers do big damage at high accuracy and immense range, so if you haven't moved them in a turn, by all means put them in Overwatch.

The big key to doing well tactically is your scouting patterns. You ABSOLUTELY want to avoid the scenario where your last guy spots the aliens right when the rest of your team has no moves left. If you do this with a Sectopod on Classic, you are probably going to wipe. This means that you usually want 1 or 2 guys scouting. They move first every turn. The rest of your team is carefully positioned such that they reveal no new terrain when moving. This is much more powerful that constantly Overwatching.