I'm a big fan of Linode but I see Linode isn't amongst the supported cloud providers. Is there some fundamental issue here or is it just lack of time / resources to develop support?
http://deis.readthedocs.org/en/rtfd-org/components/provider/
That being said, we support any provider which runs CoreOS. Deis is just an platform which utilizes Fleet, Etcd and Docker. The best place to start would be to take a look at the Quick Start documentation: http://docs.deis.io/en/latest/installing_deis/quick-start/