The winged lion has long been a traditional symbol of Venice. It is one symbol of Mark the Evangelist, who has been the is the city's patron saint ever since his remains were taken from a tomb in Alexandria, Egypt, and brought to Venice in 828 AD. Venice's original patron saint had been St. Theodore, a soldier-saint perhaps best known for battling a dragon (or, as a statue of him in Venice depicts it, a crocodile), but as Venice grew and became an important player in world affairs, it was felt that a more prestigious saint was needed. And so, St. Mark was chosen.
The lion of Venice is usually depicted with its paw on an open book that contains the text "Pax tibi, Marce, Evangelista meus." This Latin phrase translates as "Peace be upon you, O Mark, my Evangelist." Venetian legend has it that, while visiting the region of Italy that would later become the Veneto, Mark was approached by an angel, greeted with those words, and told that the Venetian lagoon would be his ultimate resting place. The actual story is most likely as described above, with the Venetians taking it upon themselves to fulfill the angel's prophecy (which they probably wrote themselves, too).
Interestingly, during times of war, the lion was depicted with a sword in one paw and the book, closed, safely kept under the other. Other depictions sometimes show a halo about the lion's head, the words on the book abbreviated to their initials, and the lion in moleca (showing only the head, top of the body, and paws). As one might expect, the lion could be found everywhere throughout the city – as statues on buildings, carved into wellheads, in patere, and every other place imaginable.
After the republic fell following Napoleon's invasion, however, over 1,000 lions were removed throughout the city in an effort to suppress Venetian pride. A Venetian stonemason was contracted to carry out their removal, but he did a poor job (undoubtedly on purpose), overlooking many of the lions in the city. The ones that did get erased left behind empty decorative panels on whatever they had previously adorned, something one can still find throughout the city today.