Sachverhalt: A. X._ wird vorgeworfen, er habe in der Strafanstalt Pöschwies im Auftrag von Mitgefangenen versucht, für sie eine schallgedämpfte Pistole, fünf Handgranaten sowie Reservemagazine mit Munition zu besorgen. Zu diesem Zweck habe er zwischen dem 12. und 15. Juni 2001 von der Strafanstalt aus acht Telefongespräche mit Personen in Serbien geführt und bei diesen die genannten Waffen bzw. -bestandteile bestellt. B. Das Obergericht des Kantons Zürich, II. Strafkammer, sprach X._ am 22. August 2003 kantonal zweitinstanzlich der versuchten Gefährdung der Sicherheit mit Waffen (Art. 260quater StGB in Verbindung mit Art. 21 Abs. 1 StGB) sowie der Widerhandlung und der Anstiftung zur Widerhandlung gegen das Waffengesetz (Art. 33 Abs. 1 lit. a WG, teilweise in Verbindung mit Art. 24 Abs. 1 StGB) schuldig. Es verurteilte ihn zu einer unbedingten Gefängnisstrafe von 10 Monaten. Vom Vorwurf der strafbaren Vorbereitungshandlung im Sinne von Art. 260bis Abs. 1 StGB sprach es ihn frei. Das Kassationsgericht des Kantons Zürich wies mit Zirkulationsbeschluss vom 10. Dezember 2003 eine kantonale Nichtigkeitsbeschwerde von X._ ab, soweit es darauf eintrat. C. X._ führt Nichtigkeitsbeschwerde mit dem Antrag, das Urteil des Obergerichts des Kantons Zürich vom 22. August 2003 aufzuheben und die Sache zu neuer Beurteilung an die Vorinstanz zurückzuweisen. Das Obergericht und die Staatsanwaltschaft des Kantons Zürich verzichten auf eine Stellungnahme zur Beschwerde. 