Another fantastic question :) Keep 'em coming! I've made a video to walk you through "Address Component Comparison":
This is using Kickstart 2 and the demo store flat rate shipping services. You can create these as you need them for each region you want a different rate.
STEP BY STEP
1) Go to admin/commerce/config/shipping and click "Add a flat rate service"
2) Name your service "Region 1" (or whatever you want) and give it a generic title, click save.
3) Click "configure component" next to your new flat rate
4) Add a condition "Order: Address component comparison"
5) Select "Shipping" address
6) Choose from the drop down a suitable filter for your region (maybe by city or province?)
7) Click "save"
Congrats! You now have an address-aware shipping rate!