There was actually, listen/notify was available back in 7.1[0][1], maybe earlier.
No payload until 9.0 though, that would usually be done by storing the payload in a dedicated table and querying that when receiving a notification.
[0] http://www.postgresql.org/docs/7.1/static/sql-listen.html
[1] http://www.postgresql.org/docs/7.1/static/sql-notify.html
edit: found the 6.4 docs, it's there: http://www.postgresql.org/docs/6.4/static/sql-listen.html
edit 2: digging in the release notes, LISTEN/NOTIFY was made to work in Postgres95 Beta 0.03: http://www.postgresql.org/docs/6.4/static/release13262.htm (and was apparently present in a non-working state in previous versions)