How do you approach centralised patch management for Linux?

Most Configuration Management tools are really good at this. puppet and Chef being two of the most popular, and radmind being the one I use.
The documentation for the specific tool will give you an idea of how to implement patch management -- it does vary from tool to tool.

Other options include a centralized yum/apt/whatever repository and homegrown scripts to pull patches from it at scheduled intervals (or on demand), and there are also commercial solutions from some major vendors, some of which (like RedHat's RHN Satellite) are quite excellent if you spend the time learning how they work and really take advantage of their capabilities.

One item nobody has pointed out yet that I feel bears noting is homogeny -- to the extent possible, make your servers interchangeable cogs running the same software. This greatly simplifies patch management (the same patches have to go everywhere) and IMHO makes life a lot easier as your environment grows.

I would recommend something along the lines of Spacewalk. It is basically the free version of Red Hat's Satellite software.