Ask HN: Trademarks - what, where, when?

I am working on my first startup and I try to devise a plan on the order of things that I should do to get my company up and running. I haven't incorporated yet. Currently, I am trying to identify: 1. What should I be trademarking - my company name will differ from my first application's name (or so I plan right now), so can I trademark only my app's name? If I don't directly provide any services or sell products through my company, but instead all this is done in the application(s) I have trademarked, is there any infringement to a trademark filed for my company name (by a another company)? (I guess there is specific answer for every country/region's law) 2. Since I plan to provide an online service accessible world-wide, where should I be filing trademark applications? Every country where I will operate? (Currently, I see as a best option to file an application for US and/or EU) 3. When should I be trademarking - when I did my research on trademark availability (in the US) for my app's name, I decided to check the trademarks of some big companies such as Apple and Facebook and to my surprise, Facebook's seems to be filed Oct. 2010 and granted in 2011. There is explicit statement for FIRST USED and FIRST USED IN COMMERCE which points to Apr. 2004, though. Does anyone know anything about such retrospective trademarking? I am trying to do my planning as agile as possible, but since my effort is to bootstrap my company, I need to plan accurately and far in advance the big expenses I will have around incorporation. Big thanks to the people that will shed some light on this distant-to-my domain of expertise topic.