lsb_release seems to be part of lsb-release package. Thus if you do an apt-get install lsb-release, you should be able to follow the documentation.
But this is kind of weird, not having this installed by default. We’ll have this investigated, and maybe the documentation updated.