Releasing All Characters
Keep beating Arcade Mode or Story Mode with different characters until everybody is released. There is no hidden 'off screen' characters. What you see is what you get.

Activating Theater Mode
The Theater Mode gets opened up after you beat Story Mode once with whatever character. At that time you are able to listen to the stage soundtracks, view the movies of the character you just beat Story Mode with and the attract movies (Arcade Intro, PlayStation2 Intro, and both EMBUs). You need to keep on beating Story Mode with different characters all ending movies. Getting all movies requires you the beat Story Mode with both Kuma and Panda.

Unlocking the Hon-Maru Stage (Dojo Stage)
Beat Force Mode once with whatever character.

Unlocking the Statue Stage
Beat Story Mode with Steve Fox

Unlocking Eddy Gordo (Christie Palette Swap)
Beat Story Mode with Christie Monteiro at least once. The select Christie using the Right Punch button and you will be able to play Eddy Gordo. Since this is a palette swap, Eddy has no moves of his own.
Only one player can be Eddy, if the second player tries to select Eddy as well you end up playing as Christie.

Unlocking Miharu (Ling Palette Swap)
Beat Story Mode with Ling Xiaoyu at least once. The select Ling using the Right Kick button and you will be able to play Miharu. Since this is a palette swap, Miharu has no moves of her own.
If the second player tries to select Miharu as well you end up with Ling Xiaoyu in her Tekken 3 School Girl outfit.

Ling School Girl Outfit
Select Ling with Right Punch after you have beat Story Mode with Ling.

Getting Your Records On The Internet Ranking Site
Beat whatever mode you would like to enter your records for using the default game settings (these are the settings colored green, such as 2 rounds or medium difficulty). Once you have beat the mode and you enter your initials press and hold Square and Triangle, then tap u/f on the joystick. You will see a password you can enter on the Japanese PlayStation2 Tekken 4 Namco site.