Wie kann ich den Vertrag für das Heim-Internet im Zusammenhang mit dem Umzug in eine andere Stadt kündigen?

Wenn du einen Flex-Vertrag (ohne Mindestvertragslaufzeit) abgeschlossen hast, so kannst du den Vertrag wie vereinbart mit einer Frist von 4 Wochen zum Ende eines Kalendermonats kündigen. Es genügt, wenn du ein unterschriebenes Kündigungsschreiben verfasst und an o2 schickst.

Wenn du dagegen einen Laufzeitvertrag geschlossen hast, so kannst du diesen nur mit einer Frist von 3 Monaten zum Ende der vereinbarten Laufzeit bzw. zum Ende der Verlängerungsperiode kündigen. Wenn du umziehst, solltest du o2 daher mit dem Umzug des Anschlusses an deine neue Adresse beauftragen (kostenpflichtig).
Bei deinem Auszug ist o2 verpflichtet, den Anschluss in der alten Wohnung zu deaktivieren. Solltest du keinen Umzugsauftrag erteilen, wird o2 dir dann die Kosten der verbleibenden Vertragslaufzeit in einer Summe in Rechnung stellen. 

Siehe auch:
https://www.o2online.de/service/internet-umzug/