This answer is aimed at non-realistic FPSes. This info is designed to assist anyone playing games like anything from the Tribes franchise, Quake, Half-Life, Unreal Tournament, etc.
NUMBER ONE: LEARN. THE. MAP.
This one is in all caps, header font and fully-written because I can't emphasize it enough. In fact I'm frankly stunned it hasn't been mentioned already except in Chase's answer and he only listed it as number 3, because this one is universal. I've been playing shooters since Doom when I was five, and I can tell you that the one thing that is consistent across all shooters -- and this includes realistic/pseudo realistic non-arena shooters like Counter-Strike or Call of Duty -- is that map knowledge will allow you to dominate anyone that does not have map knowledge. Period, end of discussion.
The importance of knowing the map layout becomes even more prominent in the arena shooters I'm targeting with this answer, for a couple of very important reasons:
- Movement is a crucial skill in these games -- a defining feature of arena shooters -- which means that terrain knowledge is a crucial skill, because it affects how well you move.
- Except in some games like Tribes, weapons and powerups spawn on the map in arena shooters. Knowing the spawn locations of these pickups is absolutely crucial. In Tribes, knowing the location of your nearest inventory station (or generator when it goes down) is just as important.
Knowing the map in shooters is the difference between coasting along the top of the map geometry at ~40 miles per hour grabbing every armor and weapon pickup along the way before everyone else can and walking around aimlessly looking for someone to shoot. The latter tends to end in loss.
2. Get good at spatial reasoning.
Arena shooters are also usually defined by their lack of hitscan (instant hit from the moment you press fire -- no projectile) weaponry. This adds another thing you have to get good at; leading your target. And your projectile's behavior is likely going to be very different depending on the weapon you use. This one is especially important in Tribes because of the combination of wide-open areas, breakneck speeds, and non-hitscan weapons -- new players sometimes have a hard time hitting anything at all in Tribes.
My advice to you is to pick one weapon and stick with it for a while. A common example is using the rocket launcher in Quake. The RL is a very versatile weapon because it has splash damage, which allows you to aim less precisely to score damage, and it can boost your mobility in a pinch -- the ubiquitous rocketjump. This makes it a weapon that is both good for newbies to pick up and highly rewarding to master. On the flipside, learning the railgun first might be a poor choice because it doesn't offer anything beyond being able to do good damage at long range, and it's also highly unforgiving when you miss (long refire time). Also, limiting yourself to one weapon whenever possible like this allows you to eschew having to learn everything at once, making the game more enjoyable while you learn it; as opposed to trying to learn every weapon at once and being terrible with all of them for a long time.
The other thing you should focus on learning when you're new to a shooter is the movement mechanics. Moving around affects your shot just as much as moving your crosshair, and it also doubles as your primary defensive measure. Fortunately, movement is usually a constant thing that doesn't change (notable exceptions include class-based team games like Team Fortress and Tribes -- in those cases I also highly suggest you stick with one class until you feel comfortable), so you only have to learn movement once to start applying your skill to each weapon.
3. Most importantly... try to have fun even when you're doing poorly. Or you'll never truly enjoy the game.
This sounds like an oxymoron if you were to apply it to most modern military shooters like Call of Duty, because when people get ahead in that sort of game, they really get ahead. Killstreak bonuses being used against you, spawning in a worse location, being spawn-camped by vehicles, even racking up money in Counter-Strike... these are all things that don't make a game fun for someone that's losing an FPS.
The easiest way to avoid this is to play team-based gametypes, with a focus on objectives instead of kills. Deathmatch being "the basic gametype" of most shooters is kind of a misnomer; I think that deathmatch is actually better described as the arena for experienced players who have achieved a high level of mastery with the fundamentals of the game like map knowledge, weapon usage, and movement mechanics. Games like CTF, attack-and-defend, king of the hill, etc. allow you to contribute to your team winning without being good at killing players. Additionally, they allow you to be helpful without knowing all of the map because objectives are usually clearly indicated on the HUD. Tribes is extremely strong in this regard, offering the entire home base defense/offense "side-objective" that anyone can pursue at any time to give their team an advantage.
Over time, you will become familiar with the fundamentals of the game, and as you enter intermediate player status you may crave "the kill," what many consider to be the purest form of competition between two players. You might find yourself stopping your pursuit of an objective just to have an intense 1v1 duel with another player. Then you can truly elevate your status to that of one who racks up ridiculous killstreaks and pulls off the occasional amazing trick-shot. Try to avoid having this attitude at the beginning of the game until you learn the basics.