A large part of prediction is knowing the map well. Oftentimes, you probably will find yourself following the same paths in an area, or employing the same tactics. For example, if I am caught by an enemy in the house on the midpoint of badlands, I'll usually try to move up the stairs in the picture to the right, to gain a height advantage, and to ensure that I have the fallback option of taking the large health pack.
Now, when you find yourself doing these things unconsciously, pay attention to them. These are habits that you fall into out of instinct, because your brain knows that they give you some sort of advantage over your opponent. You can assume, then, that other people will try the same thing. Here are some key factors in determining where an enemy will try to position themselves in a fight (in order of importance, though the first and second are somewhat interchangeable):
1. Height advantage
2. Health advantage
3. Proximity to a medic (in competitive play, you can typically predict the movement of at least one soldier by assuming that he will always try to stay near the medic, and will always aim to block the medic from fire as much as possible)
4. Escape routes (any form of cover is included. When fighting soldiers, watch for them attempting to do a horizontal RJ off a wall, as they're extremely easy targets with a wall behind them)
5. Position on a capture point
Now, these are just places that the enemy will try to get to, and that's half the battle right there. However, you also have to worry about how they will get there. For example, it might be obvious that a player in the badlands yard (the connection between the middle point and the spire) will probably attempt to get onto the point. However, there are so many different methods of doing so, it's important to pay attention to a few factors.
First and foremost, you have to know how the different classes move, and where key jumps are. For example, a scout can jump from the small cliff in the badlands yard almost all the way onto the point by utilizing their double jump. If you see a scout running up that cliff without stopping, it's a good indicator that he's going to attempt to cap the point. If you have a bit more experience, you know that there's only one "path" in the air that the scout can take, or he'll fail the jump. By aiming along this "path," you can score some sweet shots. A soldier, on the other hand, might try to RJ up the point from various positions; however, seeing him near the spire gives you an idea of what he might attempt, and thus, the advantage.
Second, you want to pay attention to how the person moves. There are several different styles of movement, which I'll try to summarize here. I'll present these styles in a ranking from least to greatest in terms of the difficulty they present to you, the attacker.
Obviously, standing still is the easiest movement pattern to predict. You might see this in engineers who have set up their base, or in medics who think they've got a good cover spot. You'll usually see inexperienced or confused players doing this. Take advantage of it as you see fit, I'm not going to say any more.
Slightly above standing still is the classic running-in-one-direction technique. Often used by players who know enough to not stand still, but are more worried about aiming than dodging, these players are just as easy to kill as those standing still, if you aim your shots. Be aware, however, that players who move in one direction will usually change directions the first time they realize that you are firing into their direction of movement. So if your enemy is strafing to your right, and you overcompensate for your aim and fire too far right of them, they'll probably start strafing left.
By far the most common "strafe pattern" (a series of left-and-right movements intended to throw off an enemy's aim) is the quick "juke step" motion. Most TF2 players fall into this movement naturally after a few months of playing, as it keeps your brain alert, and makes you a more difficult target for snipers and scouts. When playing scout or sniper, or using any hitscan weapon, you have to rely on tracking (your ability to hold the mouse over your opponent as long as possible) which is mostly contingent on personal experience. However, if playing as an explosive class, like the soldier, you don't have much difficulty. Even if you miss a direct rocket, if the enemy just continues their back-and-forth pattern, the splash will deal a significant amount of damage to them regardless.
The following three movement patterns are by far the most difficult to face. However, they are not easy, and require a TON of practice and experience to implement unconsciously. You'll see these in top-level players quite often.
1. Jumping EVERYWHERE. This is most commonly seen in scouts (See YZ50's frag vid for a great example--the second clip on coldfront is perfect)
This allows you to dodge a lot of ground-based splash damage, and gives you the ability to airstrafe as covered in this post. If you're playing as scout, you'll be an infuriatingly difficult target for all but the best aimers, and if you can successfully land shots, you'll be a great asset to your team.
2. The random strafe. For those of you who have read the Dune series, imagine how the fremen walk across the sands of Arrakis. If you employ that same completely random pattern of movement, it is absolutely impossible for your enemy (the worm!) to predict where you're going to be; they have to get lucky. This is easier to implement than the first and third strategies, because random movement doesn't require as much mental effort. However, it's easy to fall into habitual movement patterns, at which point you become highly predictable.
3. The long (quake) strafe. This strafe pattern is practically never employed in pubs, and really only seen in highly experienced TF2 players. It takes the first two strafe patterns, standing still and running in one direction, and throws in a dash of randomness. This style is heavily dependent upon the player's reaction time, as he must be able to change directions based on where the enemy is firing. By paying close attention to the weapon model of the enemy, it's actually possible to predict the direction of their shots; if you are skilled enough, you can react quickly to this information, and strafe in the other direction. By combining a staggered-rhythm strafe pattern, you throw off the enemy's ability to predict your movement even further. See this video for a great example (The game is quake live, which, like TF2, lists the Quake series as its predecessor)
A random final note that I find extremely useful: If you manage to blast a player in the air, and they begin airstrafing, they will continue moving on the ground in the same direction they were moving in midair out of habit. More than 90% of players do this, because your brain processes airstrafing differently from normal strafing, and you don't feel as predictable.
Additionally, experienced players have been through all this before. They will not fall for these patterns like a less experienced player might, so watch yourself, and happy fragging!