Frame rate

Frame rate (also known as frame frequency) is the frequency rate at which a video device produces unique consecutive images called frames. Frames are still pictures that when sequence together form a fluid animation that is the basis for all moving media. Frame rate is most often expressed in frames per second (FPS).

Low FPS will result in a "choppy" gaming experience, as far as looking like a slideshow in extreme cases. Difficult calculations (like blowing up huge loads of TNT in Minecraft) can temporarily decrease the FPS to a complete stop for some seconds.

How to check your FPS

Note that your displayed FPS might not be accurate, as the game has to render all of the info in the debug menu, so you may get an increase as soon as you close the display.

Press F3 to bring up the Debug screen. Frames per second are listed after the Minecraft version at the top left. (Note: The debug screen is known to cause more load to your system, resulting in a lower FPS than you would have without viewing the screen.)
Bring up the Options screen (press Esc), select Snooper Settings, and look for 'fps'.
Various mods have options to show the FPS without other Debug screen information.

Increasing your FPS

In Minecraft

Most of the following suggestions are configurable in the game's Options menu, accessible by pressing Esc.

Turn down your render distance. (default keys: F3 + F)
Set graphics from Fancy to Fast.
Turn off smooth lighting and clouds.
Set particles to minimal.
Set the game to full screen mode; this makes Minecraft the only window being loaded, making the game run a little bit faster.
Disable sound effects. This is particularly effective when near a large amount of sound-producing blocks (lava, flowing water) or mobs. The downside is that you could only detect hostile monsters if you can see them.
Make sure no other programs are running while Minecraft is.
Hide the HUD by pressing F1.
Looking at the sky has also been known to increase FPS. However if you are deep underground, looking down toward The Void may also.
If in multiplayer, hold down Tab ↹. This will show the online players. The more players, the more lag there will be, so this could be a problem. Note that this is mostly network lag rather than FPS processing. Try playing on singleplayer.

Outside of Minecraft

On Windows, open Task Manager and go to the processes list, find javaw.exe (the Minecraft program), right click it and set its priority to high (NOT realtime. This will cause all other programs to crash.)
On Windows, with machines that have Intel HD 4000 integrated cards, turning on advanced gl in the options menu can lead to a significant performance boost.
Put the .minecraft folder on a solid-state drive so that the world and the game itself can be loaded faster.
Do not run other programs while Minecraft is open.
Turn off Aero in Windows Vista/7.
Disable compositing (sometimes called "desktop effects") on GNU/Linux (Compiz, Kwin, Xfwm, etc.)
Update graphic card drivers and make sure antialiasing and anisotropic filtering are turned off in the driver settings.
Find ways to cool down your computer, this case is more rare but happens to some computers, mostly laptops. High temperatures (usually 80°C or higher) will cause the hardware to throttle, thus slowing down the game.
Log into a Window Manager like openbox or fluxbox instead of a desktop environment like GNOME, KDE or Cinnamon on GNU/Linux

Third party methods

These mods are not guaranteed to work and may contain malicious files or corrupt your Minecraft program. Be careful when downloading and installing them.

OptiFine is a mod which can substantially speed up and stabilize Minecraft's framerate. It has now been combined with Optimine
There are also guides available on how to manually increase FPS by editing various files in your system.
Also you are free to try Minecraft Tweaker, tool developed to install mods above and some minor tweaks.
Not exactly a mod, but using a ramdisk greatly improves the performance of Minecraft by storing the save files in RAM, which is much faster than a hard drive. However, there is some risk involved, if the computer crashes, you will lose all progress since your last backup to the hard drive.
If you have any Nvidia card, then adding minecraft to your Nvidia control panel should make framerate, also, Install Drivers for Nvidia/AMD raedon.

Render distance

The render distance controls how many chunks of the world are visible at once, and can be set from the Video Settings menu. The fewer chunks that are included, the faster each frame can be rendered, resulting in a higher FPS.

The most distant terrain is faded into the sky color as if by fog, to avoid a sharp edge to the visible world; so this option is also known as "fog".

In Minecraft Pocket Edition 0.8.0, render distances can be as far as 25 chunks (400 blocks) in addition to the far render distance option at 16 chunks. This feature was recently added to MCPE, adding a reason why graphics became better than the PC version.

Note: diameter = radius × 2 + 1

Name	View distance (radius)	Total count
Name	Blocks	Chunks	Sections
16 chunks	256	1089	17424
15 chunks	240	961	15376
14 chunks	224	841	13456
13 chunks	208	729	11664
12 chunks (default)	192	625	10000
11 chunks	176	529	8464
10 chunks	160	441	7056
9 chunks	144	361	5776
8 chunks	128	289	4624
7 chunks	112	225	3600
6 chunks	96	169	2704
5 chunks	80	121	1936
4 chunks	64	81	1296
3 chunks	48	49	784
2 chunks	32	25	400

Void Fog

Fog is a part of the environmental void fog seen as the player approaches bedrock and The Void. Void fog progressively closes in at layer 13 and below. At layer 1, the void fog begins just outside of your reach, and torches are ineffective for vision though still effective for mob stopping power. Bringing sunlight (block-based light such as torches does not affect the gloom effect) to the low layers removes this gloom effect. However, this "render distance" is only fog - it will not load less chunks, resulting in little to no FPS increase. Void fog is not present in Creative mode.