Mr. Martin, we found it peculiar that Tyrion considered the importance of the Greyjoy fleet in aCoK (when Balon's message reached him in KL), since he never thinks about the West's own naval strength and it's usefulness against the Starks.
So we began to doubt said strength.
Did Tywin ever rebuild the Lannister fleet, after Euron burned it eight years ago?
And if he rebuilt it, did he ever appoint a permanent commander of this fleet?
Yes, Lord Tywin certainly replaced the ships that were lost.
However, as far as naval power goes, the only fleets comparable to that of the Greyjoys are the royal fleet (most of it destroyed on the Blackwater) and the Redwyne fleet, based on the Arbor. Besides the king, the Greyjoys and Redwynes are the traditional sea powers of Westeros.
The lords whose lands abut the coast of the Sunset Sea all keep a war galley or three about for coastal defense, and of course those shores are home to scads of fishing boats as well. The Lannisters have a larger and much grander fleet, but we're still only talking about twenty to thirty ships, perhaps. To fight a major battle, they would call the ships of their various bannermen, just as Stannis summoned the lords of the narrow sea for the battle on the Blackwater.
For what it's worth, however, their ships would be larger and more formidable than the longships of the ironmen -- cogs, carracks, and war galleys of various sides, up to the great dromonds with scorpions and catapults on deck.
The Tyrells are in more or less the same position as the Lannisters, though they depend even more on their bannermen, especially the lords of the Shield Islands off the mouth of the Mander. The Hightowers have only a few warships, but control Oldtown, home to numerous trading vessels.