If you'd like to see some unrelated but available and open-source code to generate rhyming metric verse: http://github.com/darius/languagetoys. Unlike the paper, this doesn't even try to preserve sense -- it just uses n-gram statistics.
This gives me the bad feeling of when SIGGRAPH used to have papers on "artistic" filters (instant impressionism! instant woodcut!) by people without a feel for the expressiveness of the medium which they are simulating. Such work sometimes seems like subtle satire.
OTOH, I don't want to give the good Googlers short shrift, and it is certainly welcome to consider the meter (and maybe rhyme) of generated text.
If you'd like to see some unrelated but available and open-source code to generate rhyming metric verse: http://github.com/darius/languagetoys. Unlike the paper, this doesn't even try to preserve sense -- it just uses n-gram statistics.