Why does Messages app take up so much space? I was recently inspecting the Usage tab in my iPhone's settings. The Messages app is #2 on the list with almost 700 MB. Anecdotal reports have it that the app can take up multiple GB of space. So what is in there? 

Is every photo and video sent being stored in the app's data? If so, does that mean if I take a photo or video and send it out, it is being stored on my phone twice? And can I remove the photos and videos without deleting the entire message thread?
Yes, videos and photos are stored in messages and they take up too much space. Try deleting any large discussion thread you do not need if you would like to free some space. Or, if you would like to weed out individual photos or videos, you can tap and hold on any message bubble for the context menu. It will appear with two options: "Copy" | "More". Tap "More" for a list of checkboxes to appear on the left side of the screen. This allows you to easily delete one or more (large) individual messages.

Up to iOS 6 messages just weren't in the usage tab, and consequently one couldn't easily see how much space it consumed.

Also note, that you are just deleting those messages off of that device. If they are iMessages, and you have other devices (a Mac or OSX device) with those accounts synced there, the messages will stay there.