password-store uses git+gnupg so backing them up is a matter of distributing the git repo. My git repo lives on each of my laptops and I have a 'central' host of it...so it's backed up via distribution.

For getting passwords to my phone I use a homemade Android app + small web app that sends them to my phone encrypted on-demand from my laptop or desktop. There are Android apps for using password-store but you have to put your GnuPG keys on your phone for that and I prefer not to do that.