Open this link in MobileSafari - my_celcom.mobileconfig and install the profile. Alternatively, you can download this file and mail it to yourself and open it up in the iPhone Mail.app.
Credits go to http://help.benm.at/help.php. I downloaded the settings for SG telcos from that site to see which parts were customizable and pretty much found you just need to change the APN to use celcom3g.
EDIT: I’m on the RM68/month unlimited data plan. Is it the cheapest unlimited 3G plan around?
EDIT: I can confirm that tethering and MMS does not work on the iPhone 2G (1st-gen) right now. It will probably require jailbreaking which should be out on Friday, 19th June.
EDIT: “Does not work” means the MMS and tether options are nowhere to be found in Settings.