Amazon can be really phinicky, I don't have experience with the others. I do know I submitted my app to google playstore yesterday and it went later that day. I sent one to Amazon, they demanded my free app have more screens and features. They kept demanding so many features I got fed up with them and decided they didn't need my app? The rest of the markets, I only recognize GetJar. There's also 1Market. Only reason I know those two is a tablet we was looking at doesn't come with the play store, but 1market and getjar. From what I've seen, 1Market is not worth my time. (from a user's point of view, not developer's point). Granted, depending on your app, if your wanting to target a young kid who has a tablet their parents bought cheap and doesn't have playstore capability, 1market and getjar might be right for you! ;-)
I have been promoting my app (free) for last couple of weeks and been getting some downloads.
This is a GPS app, so I've used various travel and trekking forums in addition to the android forums. After blogging on these sites, I saw a noticeable improvement in downloads. Though not huge, its a decent no and since its a free app, I'm happy.
My next app will be a paid app so this was just a trial run.