When I try to install photoshop express into my android via the website i get a message telling me that there are no android devices assiciated with this account, but I cannot change anything. I have a HTC Desire
It worked for me on my own HTC Desire. I was already logged into my Google/Market account. Are you?
When you open your market app's account settings, or check your device's Settings > Accounts & sync > Manage accounts > Google Accounts, do you see yourself logged in?