This is actually a lot simpler in Xcode 4, but you just need to know where to get around.
First, get the CloudMade libraries as per the original instructions and check them out into your project folder.
svn co http://developers.cloudmade.com/svn/iphone-api/iphone-api/trunk/inc
svn co http://developers.cloudmade.com/svn/iphone-api/iphone-api/trunk/libs
Then go into the project settings by clicking on the project in the left hand Project Navigator. Click on Build Settings and make sure "All" is selected.
From there, add the necessary Header and Library search paths, as per the original. There seems to be a frustrating bug with Xcode and adding these paths, and it's quite inconcistent. I recommend typing them out all as one line for each section, to get around this UI bug.
$(SRCROOT)/inc/CloudMade $(SRCROOT)/inc/Proj4 ($SRCROOT)/inc/route-me
$(SRCROOT)/libs/CloudMade $(SRCROOT)/libs/Proj4 ($SRCROOT)/libs/route-me
Setup linker flags, by adjusting the "Other Linker Flags" setting. You'll find this in the same area, use the search bar on top to ease browsing :)
-ObjC -all_load -lCloudMadeApi -lMapView -lProj4
You can hit Validate Settings to ensure everything is correct.
Finally, some extra libraries and frameworks.
Click on the project and under Targets select the primary target for your project there. Click on the Summary tab and scroll down to Linked Frameworks and Libraries and click the (+) button.
Simply search for sqlite3 and you should see libsqlite3.0.dylib and you can add it.
Do the same for QuartzCore.framework and finally libstdc++.6.dylib
And that's it! You should be able to start building an application using the CloudMade SDK :)