I might be moving (prefecture) soon and thought I'd draw up a checklist for moving house. I don't have any utility company contracts but probably will in the new place. In order for this to be useful for others, any suggestions that come up I will edit this post to include here. Here's what I've come up with off the top of my head:
Moving out prodedure:
Cancel Utilities: Electricity, Gas, Water, Landline Phone, Internet
Notify City Hall of moving out (not required in some cases, if moving within the same city)
Redirect mail with Post Office
Moving in procedure:
Register Utilities: Electricity, Gas, Water, Landline Phone, Internet
Notify City Hall of moving in. Make sure your Residence Card is updated too.
Notify organisations of new address (see list below)