Der Sohn eines Rechtsanwalts war in der katholischen Jugendbewegung aktiv. Er studierte katholische Theologie in Breslau, München und Wien. Am 21. Dezember 1940 wurde Theissing durch Adolf Kardinal Bertram zum Priester für das Bistum Breslau geweiht. Er wirkte als Kaplan in Glogau.
Nach dem Zweiten Weltkrieg wurde er nach Cottbus vertrieben und wurde dann Kaplan und Jugendseelsorger in Görlitz. Seit 1953 erfüllte er verantwortungsvolle Aufgaben im Erzbischöflichen Amt Görlitz.
Am 3. März 1963 wurde er zum Weihbischof im Bistum Berlin mit dem Titularsitz Mina ernannt und am 7. Mai 1963 durch den damaligen Bischof von Berlin und späteren Kardinal, Erzbischof Alfred Bengsch, geweiht. Theissing wurde am 12. Februar 1970 zum Koadjutor des Bischöflichen Kommissars in Schwerin Bernhard Schräder ernannt und folgte diesem im Amt nach dessen Tode am 10. Dezember 1971. Am 23. Juli 1973 wurde er zum Apostolischen Administrator von Schwerin erhoben. Am 5. Dezember 1987 trat er von diesem Amt zurück.
Heinrich Theissing betrieb besonders die Seligsprechung von Nils Stensen, die er am 23. Oktober 1988 in Rom miterleben konnte. Kurz nach seiner Rückkehr starb er.
Theissing war der Hauptkonsekrator des Bischofs Norbert Werbs.