but I can't find any information about a)how to actually find a host which has Dancer and other Perl related web app functionality available

It's unlikely you'll find any Dancer-specific hosting. Most hosting services just support Plack, but that's fine since Dancer is based on Plack. How do you find them? Well, with your search engine of choice. I searched for cloud hosting perl plack, and the first hit already pointed to three different hosters.

I also dimly recall that Heroku supports Perl, might be worth investigating too.

All those cloud hosting services publish instrunctions on how to deploy your application to them.