Where are the StarCraft 2 replay videos stored and can I share them?

Yes, they are in a directory such as:

C:\Documents\StarCraft II\Accounts\[number]\[other]\Replays

The cool thing is that the replay files themselves are quite small (11-15 KB on my computer) so it should be easy to email and share. Another cool thing is that SC2 registers the ".SC2Replay" file extension, so all you need to do is double click on the file to play it - you (or your friend) don't even need to copy it into their own "Replays" directory.

On OS X as of patch 1.1:

/Users/[You]/Library/Application Support/Blizzard
/StarCraft II/Accounts/[Account]/[Profile]/Replays.

Before patch 1.1 the StarCraft II folder was located in /Users/[You]/Documents instead of under Application Support.

Unfortunately, while opening a .sc2replay file in OS X will launch the game, it won't auto-start the replay. You'll have to move it to your Replays folder and use the in-game UI to start it.

Windows 7:

C:\Users\[USER]\Documents\StarCraft II\Accounts\[number]\[other]\Replays