The PWM signal is generated by timers on the AVR chips. Each timer can generate a PWM signal on two or three different pins. Each pin can have it's own duty cycle, but they share the PWM frequency. You can change the frequency of the PWM by changing the clock source for the timers. By default they use the CPU clock divided by 64, ie. they have their prescaler set to 64 by Arduino initialization code.
To confuse things more there are two different PWM modes: fast PWM and phase correct PWM. In fast PWM the timer counts to 255, then overflows and starts over from 0 (256 different states). In phase correct PWM the timer counts to 255, then changes direction and counts downwards to zero, changes direction and so on (510 different states).
The Arduino Mega has 5 timers, timer0 - timer4. Because timer0 is also used for the millis and micros functions it uses fast PWM, whereas the other timers are configured for phase correct PWM. This results in different frequencies on different pins:
Pin 4 and 13, controlled by timer0:
16 Mhz / 64 / 256 = 976.56 Hz
Other PWM pins, controlled by timer1-4:
16 Mhz / 64 / 510 = 490.20 Hz
The calculation is: Clock / Prescaler / PWM mode number of states
The situation is the same for all other Arduino boards I know of, except they have less timers that connect to different pins.
You can change the PWM frequency by changing the timer prescaler. See this page: http://playground.arduino.cc/Main/TimerPWMCheatsheet
It is also possible to make the timers count to a different value than 255. On the 8 bit timers you will loose an output pin, but on the 16 bit timers you can use the Input Capture Register to define a TOP value. The input capture functionality is a feature rarely used in the Arduino community so you likely won't miss it.
The Arduino libraries only allow you to use 8 bit resolution, even on the 16 bit timers. If you want the higher resolution, you will have to write your own analogWrite, or use a library made for the purpose.
On the Arduino Mega timer0 and timer2 are 8 bit, while the rest are 16 bit.
By changing the mode of the 16 bit timers to make use of the full resolution, in combination with changing the prescaler and the TOP value, you can achieve a very wide range of PWM frequencies.
The maximum frequency you can achieve is clock / 4, by setting the prescaler to 1 and TOP to 3 in fast PWM mode - a lower value isn't allowed. This will give you a 4 MHz PWM with 2 bit resolution. It can be on 0%, 25%, 50%, or 75% of the time. A higher TOP value will give you a higher resolution at a lower frequency.
For a longer explanation read this article or refer to the datasheet.
Changing the prescaler, PWM mode, or TOP value for timer0 will mess with