If the thief uses the device with another sim or cellphone service would it still be tied to my iCloud?
There is no relation between the carrier's plan for cellular services (which is tied to your carrier) and iCloud (which is a service from Apple). So even if you cancel your phone plan after it's stolen, the iCloud linkage that was established when you setup your phone (or later modified it) would continue to remain with Apple.
If your iPhone is running iOS 7 and you have Find my iPhone turned on (Settings > Privacy > Location Services > Find my iPhone), then the person who has your phone cannot erase it or use it without your iCloud account and password.
If your iPhone is lost, you can visit http://www.icloud.com, login with your iCloud account (the one setup on your iPhone) and use Lost Mode (which prevents activation of the phone without your iCloud account credentials and also allows you to send a message to the device) or Erase iPhone (which erases your iPhone remotely).
They can't necessarily access your data and account if it's logged out on the phone. I suggest changing passwords you think might be saved so that it forces them to be re-entered.
On the iCloud website, you might be able to disable your iPhone permanently until they use your password.
You can access all iCloud and Apple services through the various websites or on other devices like a Mac or iPod/iPad. Maybe you have Find My iPhone and can access that app through the iCloud website?