NOTE: Most of these suggestions are provided for Windows users, as I don't have a MAC machine, I have no clue how to change anything about them outside of the game environment. Perhaps a MAC user could be kind enough to post similar steps for other MAC users. (I am assuming that if your smart enough to get WoW running on a UNIX box that you won't have these issues, or will already know how to sort them.)

Q: What is FPS?
A: FPS is short for Frames per Second, this means the number of times the image on your screen is refreshed.

Q: How does my FPS affect me?
A: FPS, affects your gameplay in a few ways, the most prominent of which being that you have smooth gameplay, if your FPS drops below about 15-20, you may find many games unplayable, as the screen doesn't change often enough to reflect recent events or your movements. However when tweaking your FPS its easy to 'over-tweak' meaning that your increases in FPS don't actually make a difference any more, for most people this point is between 55 and 75, namely because the refresh rate of the majority of monitor's/screens falls between these numbers. (The average human eye can only detect changes up to about 60 times a sec, if something is changing more than 60 times a second, then it will blur (this is actually how HUD systems work on Fighter Jets.))
Having a low FPS can result in a negative impact on your performance, as you will take longer to react to things, such as moving out of fires, void zones etc... or even just casting spells etc... in succession.

Q: How is my FPS affected?
A: FPS is based on a number of both hardware and software variables, for instance, having a lot of processes running consuming allot of processing power will result in a lower FPS rate.
Things like CPU, GPU and memory are the main hardware modifiers for your FPS, games like WoW which run on a rather archaic game engine, are mainly based on the CPU, unlike most of the more modern games which primarily render on the Graphics Card or GPU. Simply put, you can have the best Graphics Cards in the world, but you still may not see any difference in WoW when compared to someone who is using a card between 2 and 5 years older. 

Q: How does WoW run?
A: As mentioned before, WoW runs almost solely on the CPU, meaning that small increases in CPU performance will have a big impact on how smooth your game runs. At this point in time, WoW also only supports running on 2 cores, so those of you with quad cores (while you shouldn't be experiencing any FPS issues) may find that setting process affinities better, results in a fair increase in your FPS. by default WoW will run on the first 2 cores it sees, (affinity setting 3) meaning cores 1 and 2, and threads on the WoW technical forums suggest that it is advisable to keep it to this.


That's the raw basics on FPS below I will list a relatively short list of things you can do to increase your FPS with minimal cost.

1) With World of Warcraft running, open task manager, click on the Applications tab, right click wow.exe and click 'Go To Process' this will take you to the 'Processes' tab which lists (almost) all the processes currently running on your computer. The process Wow.exe should at this point be highlighted, simply right click it and hover over 'Set Priority' then click 'High', your computer will now dedicate a higher number of cycles to the process Wow.exe meaning that WoW will respond to changes more frequently. Close the task manager and play away.
[color=red][b]NOTE: DO NOT SET ANY PROCESS TO 'Realtime' this will dedicate 100% of your CPU usage to that process.... so while it will run perfectly, you wont be able to interact with it.[/b][/color]

Example:
[img]http://wanted-my.info/wow/fps/task.PNG[/img]

2)
Video:
 While in game (or on the login screen) open the Video options and set Multi sampling to 1x and the Screen Resolution to 1024x768. You can use different resolutions but I've found this provides the best compromise between FPS and quality. If you need some more screen space, you can always use the UI scale slider. It is advisable to try running WoW in both Windowed and Full Screen modes, and different people experience different results, in theory however, applications/games will always perform better in Full Screen mode.

Example:
[img]http://wanted-my.info/wow/fps/1.PNG[/img]
[img]http://wanted-my.info/wow/fps/2.PNG[/img]

You may notice that in my example, I have VSync turned off, You ONLY need this if you experience 'screen tearing' I.E. frames overlap each other making things appear misaligned. Turning VSync off can often net an FPS increase without any negative effect whatsoever, If you experience Screen Tearing its probably a good idea to turn this back on however.
[size=9]-See: http://en.wikipedia.org/wiki/Screen_tearing[/size]

Effects:
It's probably easier for me to explain each variable one at a time so here goes:
View Distance - This slider controls how far into the distance you can see, with the advent of patch 2.4.3 this sliders effect has doubled, so if you had the slider on max before that patch, you will be able to see (in theory) twice as far as you could before that patch. Moving this slider to the left reduces how far you can see, but it also reduces the number of things that need to be rendered on the screen, can have drastic effects on your FPS.
[b]Environment Detail[/b] - This slider controls how far in the distance you can see individual objects (closely related to View Distance). To save myself repeating myself, simply read View Distance (as their pretty much the same).
[b]Texture Resolution[/b] - This slider controls texture detail, this can have a huge impact on your FPS, however setting this to low (it only has two settings, Low or High) can make many things appear blurred. (Generally doesn't net a large enough FPS increase to be considered as a viable option)
[b]Terrain Detail [/b]- See Texture Resolution
[b]Ground Clutter Density[/b] - This slider controls how much 'clutter' such as grass, weeds and other general 'doodads' which are relatively small in size, there is on the ground :P (surprising that huh) It is rumoured to allow gatherers the ability to see gatherables that are further away.
[b]Texture Filtering[/b] - See Texture Resolution
[b]Spell Detail[/b] - This slider controls how much detail is shown for each spell, has massive effects on your FPS during fights, most notably of which AoE groups. This slider is best set at about half way, decrease with care, as you may be unable to see many effects such as Blizzard, Rain of Fire, Void Zones etc... if this is set too low, although on many systems if this is set too high, the same will apply as you may be lucky to get 1FPS during a raid encounter.
[b]Ground Clutter Radius[/b] - This slider controls how far away ground clutter may appear. See Ground Clutter Density.
[b]Weather Intensity[/b] - This slider controls how intense the in-game weather is, basicly, how much rain, snow, fog etc.. there is displayed on the screen. Personally I have this set to minimum, as it can have negative effects on your gameplay.
[b]Shadow Quality[/b] - This slider controls the quality of character and environment shadows (introduced again in patch 2.4.3) This can have a massive impact on your FPS. Personally I have this set to 0, as I don't really care much for shadows, and it doesn't really enhance the game in any way, setting this to high, allows the usage of dynamic shadows, meaning that shadows will be drawn out as they would appear during different times of day, setting this to low, just means that shadows will appear as circles or ovals beneath each character. This effect is better suited for FPS games, where shadows can make the difference between life and death.

Example:
[img]http://wanted-my.info/wow/fps/3.PNG[/img]

3) If you are still experiencing issues, It may be an idea to clean out your WoW Directory, Open it up and run the Repair.exe utility, with all the boxes ticked and click Reset and Check files.
This will reset your game to all the default settings, and remove any customisation. So make sure you have a backup of your WTF and Interface folder if you use any add-ons, or have changed things like the chat frame(s).

Example:
[img]http://wanted-my.info/wow/fps/repair.PNG[/img]



Tools used to check your FPS:
FRAPS
This is by far the most popular program to gauge FPS, and indeed record various things happening on the screen, to create movies/videos of things you do in various games. (Also creates graphs which can be used to see how your FPS changes over time)
[url]http://www.fraps.com/[/url]

In-Game add-ons such as FuBar, Titan Panel, TinyStats can all be used to show what your FPS is at any given time in the game environment without needing to run an additional program before running WoW.

This is by no means an exhaustive set of suggestions, and there are no guarantees any of them will work. The worst you can do is waste time trying them, and then reverting back to what you had before.

On a side note, Windows Vista and Windows7 users have often reported that either running WoW as Administrator or turning off UAC (the former being more advisable than the latter), gives a performance increase. I can only assume this is because it prevents allot of read/write errors the game gets but doesn't actually report to the user.
Note also that if you do set WoW to run as Administrator, you may need to configure any programs which you use while in-game or provide overlays, such as Ventrilo, TeamSpeak, VoiceOverlay, to also run as Administrator.

If you think I've missed anything major, feel free to add it :)