If my iPhone was stolen and I decide to cancel my phone plan, would it still show up on my iCloud? 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).

Also see:
iOS 7: Activation Lock + Find My iPhone
How To Enable Activation Lock On Your iPhone And iPad (iOS Tips)