Sachverhalt:
A. Der 1962 geborene K._ war als Hilfsgipser tätig und über seinen Arbeitgeber bei der Schweizerischen Unfallversicherungsanstalt (SUVA) obligatorisch gegen Unfallfolgen versichert, als ihm am 24. August 1999 bei der Arbeit eine Feuerschutzplatte auf den Kopf fiel. Die SUVA anerkannte ihre Leistungspflicht für die hiebei erlittenen Verletzungen, gewährte Heilbehandlung und richtete Taggeld aus. Am 7. August 2001 verfügte die IV-Stelle des Kantons Zürich, bei welcher sich K._ ebenfalls zum Leistungsbezug angemeldet hatte, ab 1. August 2000 bei einem Invaliditätsgrad von 100 % eine ganze Rente der Invalidenversicherung (IV). Mit Verfügung vom 26. März 2002 sprach die SUVA dem Versicherten für die verbliebenen Folgen des Unfalls von 1999 ab 1. April 2002 eine Invalidenrente der Unfallversicherung (UV) entsprechend einer Erwerbsunfähigkeit von 100 % zu, dies als Komplementärrente zur IV-Rente. Zudem bezahlte sie ihm gestützt auf einen Vergleich eine Integritätsentschädigung auf der Grundlage einer Integritätseinbusse von 20 %.
Im Rahmen eines IV-Rentenrevisionsverfahrens holte die IV-Stelle ein polydisziplinäres medizinisches Gutachten des Instituts Z._ vom 5. Januar 2010 ein. Am 10. Juni 2010 verfügte sie, die IV-Rente werde auf das Ende des der Verfügungszustellung folgenden Monats eingestellt, da der Invaliditätsgrad aufgrund einer seit der Rentenzusprechung eingetretenen wesentlichen gesundheitlichen Besserung nurmehr 29 % betrage.
Die SUVA unterzog die von ihr ausgerichtete Invalidenrente ebenfalls einer Revision. Sie setzte die Rente mit Verfügung vom 23. Juli 2010 ab 1. August 2010 nach Massgabe einer Erwerbsunfähigkeit von noch 38 % herab. Daran hielt der Unfallversicherer auf Einsprache des Versicherten hin fest. Die SUVA führte hiebei aus, die Erwerbsunfähigkeit werde damit immer noch zu hoch angesetzt, was als Entgegenkommen zu betrachten sei (Entscheid vom 3. November 2010).
B. K._ erhob gegen den Einspracheentscheid vom 3. November 2010 Beschwerde. Im Beschwerdeverfahren legte er u.a. ein von ihm eingeholtes interdisziplinäres Gutachten der Unabhängigen medizinischen Gutachtenstelle U._ vom 27. Januar 2011 auf. Das Sozialversicherungsgericht des Kantons Zürich wies die Beschwerde mit Entscheid vom 22. März 2012 ab.
Mit einem weiteren Entscheid vom gleichen Datum wies das Sozialversicherungsgericht auch die von K._ gegen die Verfügung der IV-Stelle vom 10. Juni 2010 eingereichte Beschwerde ab.
C. Mit Beschwerde in öffentlich-rechtlichen Angelegenheiten lässt K._ hauptsächlich beantragen, in Aufhebung des vorinstanzlichen Entscheides betreffend UV sei ihm "weiterhin eine volle Invalidenrente zuzusprechen gestützt auf einen Invaliditätsgrad von mindestens 70 %"; eventuell sei die Sache zur Einholung eines neuen polydisziplinären Gutachtens an die SUVA zurückzuweisen. Zudem sei diese bei Gutheissung der Beschwerde zu verpflichten, die Kosten des Gutachtens der Gutachtenstelle U._ zu bezahlen.
Die vorinstanzlichen Akten wurden eingeholt. Ein Schriftenwechsel wurde nicht durchgeführt.
K._ erhebt auch gegen den vorinstanzlichen Entscheid betreffend IV Beschwerde. Über diese entscheidet das Bundesgericht mit Urteil vom heutigen Datum im Verfahren 8C_399/2012.

Erwägungen:
1. Die Beschwerde in öffentlich-rechtlichen Angelegenheiten kann wegen Rechtsverletzung gemäss Art. 95 und Art. 96 BGG erhoben werden. Das Bundesgericht wendet das Recht von Amtes wegen an (Art. 106 Abs. 1 BGG). Es kann die Verletzung von Grundrechten und von kantonalem und interkantonalem Recht nur insofern prüfen, als eine solche Rüge in der Beschwerde vorgebracht und begründet worden ist (Art. 106 Abs. 2 BGG).
Im Beschwerdeverfahren um die Zusprechung oder Verweigerung von Geldleistungen der Militär- oder Unfallversicherung ist das Bundesgericht nicht an die vorinstanzliche Feststellung des rechtserheblichen Sachverhalts gebunden (Art. 97 Abs. 2 und Art. 105 Abs. 3 BGG).
2. Streitig und zu prüfen ist, ob die seit April 2002 ausgerichtete Invalidenrente der UV zu Recht nach Massgabe einer Erwerbsunfähigkeit von nurmehr 38 % revisionsweise herabgesetzt wurde.
Das kantonale Gericht hat im angefochtenen Entscheid die Bestimmungen und Grundsätze über die revisionsweise Erhöhung, Herabsetzung oder Aufhebung einer Invalidenrente der UV infolge erheblicher Änderung des Invaliditätsgrades, insbesondere bei einer Verbesserung des Gesundheitszustandes, zutreffend dargelegt. Darauf wird verwiesen.
3. Ob eine rentenrevisionsbegründende Änderung eingetreten ist, beurteilt sich, wie die Vorinstanz zutreffend erkannt hat und unbestritten ist, in zeitlicher Hinsicht durch einen Vergleich mit den Verhältnissen welche im Zeitpunkt der rentenzusprechenden Verfügung vom 26. März 2002 gegeben waren.
4. 4.1 Gemäss dem angefochtenen Entscheid erfolgte die Rentenzusprechung auf der Grundlage einer 100 %igen Arbeitsunfähigkeit, hervorgerufen durch ein chronifiziertes zervikozephales und -brachiales Schmerzsyndrom mit ausgesprochenen Myotendinosen und Kopfschmerz sowie durch ein chronifiziertes depressiv-somatisches Schmerzsyndrom bei Status nach axialem Halswirbelsäulentrauma und Commotio cerebri. Das ist, nach Lage der Akten zu Recht, nicht umstritten.
4.2 Das kantonale Gericht gelangte sodann zum Ergebnis, seit der Rentenzusprechung habe sich der Gesundheitszustand des Versicherten in rentenrelevanter Weise verbessert. Es bestehe deshalb nurmehr eine 20 %ige Arbeitsunfähigkeit in einer leidensangepassten Tätigkeit.
Die Vorinstanz stützt sich hiebei auf das Gutachten des Instituts Z._ vom 10. März 2010. Darin werden gestützt auf psychiatrische, orthopädische, neurologische und kardiologische Untersuchungen sowie auf eine internistische Besprechung und einen multidisziplinären Konsensus folgende Diagnosen mit Einfluss auf die Arbeitsfähigkeit gestellt: Chronisches zervikozephales Schmerzsyndrom mit Begleitsymptomatik von Schwindelbeschwerden und beidseitigem Tinnitus; koronare 2-Ast-Erkrankung. Unter den Diagnosen ohne Einfluss auf die Arbeitsfähigkeit wird eine Schmerzverarbeitungsstörung und Symptomausweitung erwähnt. Zusammenfassend wird sodann ausgeführt, in der angestammten Tätigkeit bestehe seit dem Unfall vom August 1999 bleibend eine volle Arbeitsfähigkeit. Für körperlich leicht bis gelegentlich mittelschwere adaptierte Tätigkeiten sei der Versicherte nunmehr vollzeitlich arbeitsfähig mit einer um 20 % reduzierten Leistung, entsprechend einer zumutbaren, effektiv verwertbaren Arbeitsleistung von 80 %. Die Verbesserung liege namentlich auf psychischer Ebene. Diesbezüglich seien keine Einschränkungen der Arbeits- und Leistungsfähigkeit zu finden. Insofern müsse trotz eines in der Zwischenzeit erlittenen kardialen Ereignisses von einer deutlichen Verbesserung des medizinischen Zustandsbildes ausgegangen werden.
Die von den Experten des Instituts Z._ erwähnte koronare Erkrankung hat die Vorinstanz als unfallfremd und daher nicht rentenrelevant beurteilt.
4.3 Der Beschwerdeführer rügt zunächst, IV-Stelle, SUVA und Vorinstanz hätten seinen Anspruch auf rechtliches Gehör verletzt.
Das kantonale Gericht hat die Einwände betreffend das Verfahren vor der IV-Stelle verworfen. Im heutigen Urteil 8C_399/2012 gelangt das Bundesgericht ebenfalls zum Ergebnis, dass die Rügen unbegründet sind. Das betrifft auch die Einholung des Gutachtens des Instituts Z._ und hat erst recht für das vorliegende Verfahren zu gelten, in welchem der Unfallversicherer diese Expertise zulässigerweise beigezogen hat.
Entgegen der Auffassung des Beschwerdeführers hat die SUVA seinen Gehörsanspruch nicht verletzt, indem sie nach Vorliegen des Gutachtens des Instituts Z._ keine eigenen medizinischen Abklärungen mehr getroffen hat. Auch bei der übrigen Vorgehensweise des Unfallversicherers liegt keine Gehörsverletzung vor.
Es trifft sodann nicht zu, dass sich der vorinstanzliche Entscheid ungenügend mit den Vorbringen des Beschwerdeführers auseinandersetzt. Hier liegt somit ebenfalls keine Gehörsverletzung vor.
4.4 Geltend gemacht wird weiter, bei der Einholung des Gutachtens des Instituts Z._ seien die Grundsätze gemäss <ref-ruling> nicht eingehalten worden.
Diesen Einwand hat das kantonale Gericht mit einlässlicher und zutreffender Begründung, auf welche verwiesen wird, als unbegründet beurteilt. Damit kann offen bleiben, ob und bejahendenfalls inwieweit eine Verletzung der Grundsätze gemäss <ref-ruling> in einem Verfahren der UV, in welchem das Gutachten lediglich beigezogen wird, überhaupt zu beachten wären.
4.5 Der Versicherte erhebt sodann inhaltliche Einwände gegen das Gutachten des Instituts Z._ und die darauf gestützte Beurteilung des kantonalen Gerichts. Er beruft sich dabei auch auf die von ihm eingeholte Expertise der Gutachtenstelle U._.
4.5.1 Geltend gemacht wird zunächst, das kantonale Gericht habe die Unfallkausalität der Herzerkrankung zu Unrecht verneint. Der Einwand ist unbegründet. Selbst im Gutachten der Gutachtenstelle U._ wird nicht von einer unfallbedingten Genese des Leidens ausgegangen. Weiterungen dazu erübrigen sich, zumal die Vorinstanz die Herzerkrankung zwar als unfallfremd betrachtet, dies aber nicht zum Anlass genommen hat, von der dieses Leiden einschliessenden Beurteilung der Arbeitsfähigkeit durch die Experten des Instituts Z._ abzuweichen.
4.5.2 Der Beschwerdeführer vertritt sodann die Auffassung, es sei nicht auf die Expertise des Instituts Z._, sondern auf das Gutachten der Gutachtenstelle U._ und die darin bestätigte Arbeitsunfähigkeit von 70 % für leidensadaptierte Tätigkeiten abzustellen.
Das kantonale Gericht ist zum Ergebnis gelangt, dass das Gutachten des Instituts Z._ beweiswertig ist und mehr zu überzeugen vermag als die Expertise der Gutachtenstelle U._. Diese Beurteilung beruht auf einer sorgfältigen Würdigung der medizinischen Akten. Die Vorinstanz hat einlässlich und überzeugend dargelegt, weshalb es keine Veranlassung sieht, vom Gutachten des Instituts Z._ abzuweichen.
Die Vorbringen in der Beschwerde rechtfertigen keine andere Betrachtungsweise. Namentlich ist das Gutachten des Instituts Z._ hinreichend aktuell für die vorzunehmende Beurteilung. Sodann beruhen die Feststellungen der Experten des Instituts Z._ auf genügend eingehenden und diversifizierten Untersuchungen. Das gilt auch in psychiatrischer Hinsicht. Festzuhalten bleibt, dass sich der Expertise der Gutachtenstelle U._ nur wenig objektivierbare Beschwerden entnehmen lassen und es darin auch an einer einlässlichen und nachvollziehbaren Auseinandersetzung mit den Aussagen der Gutachter des Instituts Z._ fehlt. Es ist daher nicht zu beanstanden, dass die Vorinstanz sich deswegen zu keiner anderen Beurteilung veranlasst sah. Die übrigen medizinischen Akten, einschliesslich der letztinstanzlich nochmals aufgelegten, führen ebenfalls zu keinem anderen Ergebnis. Von weiteren medizinischen Abklärungen ist abzusehen, da sie keinen entscheidrelevanten neuen Aufschluss erwarten lassen. Es kann im Übrigen auf die schlüssigen Erwägungen des kantonalen Gerichts verwiesen werden.
Die vorinstanzliche Beurteilung von Gesundheitszustand und noch gegebener Arbeitsfähigkeit ist demnach nicht zu beanstanden.
5. Ausgehend vom dargelegten medizinischen Sachverhalt hat die SUVA einen Einkommensvergleich nach Art. 16 ATSG vorgenommen und ist zum Ergebnis gelangt, die Erwerbsunfähigkeit betrage nurmehr 38 %. Das kantonale Gericht ermittelte eine Erwerbsunfähigkeit von 35 % und sah sich deswegen nicht veranlasst, vom Ergebnis der SUVA abzuweichen.
Der Versicherte macht geltend, die SUVA habe bei der Bestimmung des ohne unfallbedingte gesundheitliche Beeinträchtigung mutmasslich erzielbaren Einkommens (Valideneinkommen) seinen Anspruch auf rechtliches Gehör verletzt. Er begründet dies aber nicht weiter. Damit kann offen bleiben, ob eine allfällige Gehörsverletzung nicht ohnehin spätestens im vorinstanzlichen Verfahren geheilt worden wäre.
Eingewendet wird weiter, das trotz unfallbedingter gesundheitlicher Beeinträchtigung zumutbarerweise noch erzielbare Einkommen (Invalideneinkommen) sei nach Massgabe der in der Beschwerde postulierten Arbeitsunfähigkeit herabzusetzen. Diesbezüglich hat es mit der Feststellung sein Bewenden, dass es nach dem zuvor Gesagten bei der Arbeitsunfähigkeit gemäss dem angefochten Entscheid bleibt.
Die vorinstanzliche Beurteilung ist ansonsten unbestritten und gibt keinen Anlass zu weiteren Bemerkungen. Die Beschwerde ist daher abzuweisen. Aufgrund der Bindung des Bundesgerichts an die Parteianträge (Art. 107 Abs. 1 BGG) ist nicht zu prüfen, ob die Erwerbsunfähigkeit nicht allenfalls noch tiefer anzusetzen wäre, als dies SUVA und Vorinstanz getan haben.
6. Der Antrag, die SUVA habe die Kosten des Gutachtens der Gutachtenstelle U._ zu übernehmen, wurde nur für den Fall gestellt, dass die Beschwerde im Rentenrevisionspunkt gutgeheissen werde. Das trifft wie dargelegt nicht zu. Damit hat es bezüglich des Kostenantrages sein Bewenden und es kann offen bleiben, ob auf das Begehren überhaupt eingetreten werden könnte.
7. Die Kosten des Verfahrens sind vom unterliegenden Beschwerdeführer zu tragen (Art. 66 Abs. 1 BGG).

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird abgewiesen.
2. Die Gerichtskosten von Fr. 750.- werden dem Beschwerdeführer auferlegt.
3. Dieses Urteil wird den Parteien, dem Sozialversicherungsgericht des Kantons Zürich und dem Bundesamt für Gesundheit schriftlich mitgeteilt.
Luzern, 31. August 2012
Im Namen der I. sozialrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Ursprung
Der Gerichtsschreiber: Lanz