How do I make a modern(ish) map with photoshop?

[Freodin]

Does anyone know how to add longitude and latitude to a map?

That does indeed depend on the kind of projection you want to use.
With a simple equirectangular projection, you can just do a grid. For anything more fancy, I like to use NASA's G.Projector. It allows you to chose your projection, add your grid and export it to work on in PS. Whether you use the exported pic directly or use it as a template to work on is your decision.