On one of the loading screens of Skyrim, I saw a horse and it said that they are useful for long distance transportation in the Skyrim world. However, looking through the current big city I was in I was unable to find any horses! Do I need to catch them in the wild? Did I miss something?
Look for the stables outside of the major cities. You can buy them there.
You can see where the stables are in relation to you (if there are any nearby) by keeping an eye out for the following horseshoe icon in your HUD compass:
They also show up with a similar icon on your map:
And finally, here's what the stables look like when you're in visual range:
You can also steal horses (found at stables or in the wild), but there's a 50 gold bounty placed on your head each time a guard is made aware of you mounting one. Stolen horses also run away when dismounted, while owned horses stay where you leave them.
You can take a horse from Whiterun Stormcloack Camp just north of High Hrothgar, right under the mountain. Leaves when you dismount, comes back when you fast travel.
There is also the opportunity to get a free white horse named Frost (if you succeed at a Persuasion attempt) at the completion of "Promises to Keep," a quest to retrieve ownership papers for said horse. Look for Louis Letrush in the Bee and the Barb in Riften.
There's a second opportunity for a free horse on Katla's farm, south of Solitude. If you farm a bunch of leeks and potatoes and such for her to raise her disposition, she'll let you ride her horse(s) away, anytime you want.
If you complete the quest The Cure for Madness from the Dark Brotherhood (Spoiler) you'll receive Shadowmere as a reward.