So Google removed the support for NPN from Chrome and only supports ALPN now. ALPN is only available in OpenSSL 1.0.2 and above. At this time, only Ubuntu 16.04 ships with this version.

I'm running Ubuntu 14.04.

And so, as for a lot of other people, all of my websites were back to HTTP/1.1. Goodbye tomorrow. Luckily, there exists a version of nginx that is already compiled against OpenSSL 1.0.2. It is available here (stable branch). After adding this repository and an apt-get update i was able to install nginx. On one of my servers.

On another one (this one), I couldn't manage to update OpenSSL. After a while it turned out, that the main difference on this server is, that, in opposite to the other one, I don't have the ondrej PHP-repository in my list. After adding it, OpenSSL upgraded flawlessly, and so did nginx.

Finally! But instead of seeing my site being delivered in HTTP2, I was greeted with a friendly ERR_SPDY_INADEQUATE_TRANSPORT_SECURITY from Chrome.

I searched around and a little help of The Internet revealed that my ssl_ciphers were using obsolete algorithms. So I fixed the line to
ssl_ciphers 'ECDHE-RSA-AES128-GCM-SHA256:AES256+EECDH:AES256+EDH';
and voila, there it is again.

In brief:
add-apt-repository ppa:fxr/nginx-alpn add-apt-repository ppa:ondrej/php apt-get update apt-get upgrade apt-get install nginx

Be careful, this can have a lot of side effects. It might replace your PHP version (if you want to use PHP7 on Ubuntu 14.04 you should add this repository anyway). Your mileage may vary. Don't say I didn't warn you.

Good luck!

Update: I found this gist, you might have less side effects if you take this ppa instead of ondrej/php to upgrade your OpenSSL.