As a pilot flying a modified CATIIIB capable (but not allowed in some countries for us as we didn't certify it in all the countries we fly to yet) 737-800, there is quite a costly process in my opinion and here are some of the modifications made:
Replaced our backup instruments with digital ISFD and all the rewiring required for the ISFD (it provides 3rd source of data for autoland).
Installed the collins EDFCS-730 autopilot system on our first overhaul after delivery from previous customer.
There was an extra C/R (clear/recall) button on the usually blanked button slots beneath the ENG, SYS buttons near the autobrake selector. Functions as a clear/recall for text on the engine display like on the 777, quite cool.
Installed the collins 2274-COL-AC1-07 software package on our FMCs.
Installed GLU-925 GPS landing system (not sure if this is required, not a tech)
Installed APN-241K real-time terrain tracking radar (for mountain approaches in unmapped areas), probably not a requirement in most airline's operating conditions, but is needed for our mountain operations
Custom HUD installed, probably also not required but we are damn lucky to get one (two acutally-one of the 6 dual HUD 737s in the world) in out jets after a negotiation on lowered salaries (to pay for these systems)
New autopilot rudder servo and rudder channel in the autopilot (comes with the collins package)
And a few more, probably autoland unrelated mods, I'll go have a talk with the tech next time I'm on the line.
Also, you need CFM56-7B27E engines for single engine CATIIIB autoland, unless you are landing with the landing weight below 60,000kg since you have to use flaps 30 for autoland, therefore go-around at flaps 15. At max landing weight with the -7B27E engine and bleeds off landing, the -800 would yield only a 1.2% go around gradient so you may be more limited in weight at some airports and conditions if using CATIIIB single engine autoland with lower thrust engines. Short field package for 737NG can help improve the go-around gradient slightly due to less slats deployed but most airports without mountains around shouldn't be a problem. Our 737NG's don't go near max weights at those critical places so we didn't get the short field package.
Some airports may not be CATIIIB certified, especially the rural airports that some NG's fly into as they don't have CATIIIB lighting on their runways & taxiways (most of them), but since we don't usually fly passengers and operate on a special license, the runway lighting issue is not a problem in some countries for us.