Is it correct to say “在手机”？ Would it be correct to use the phrase "在手机”/“在手机上” etc. to express that I am doing something on my phone? For example, could I say


  我听音乐在我的手机上。


Or can 在 only be used for my actual physical location? If so, how would I express this sort of thing? (Phrases like "on the internet", "on my computer", "on my phone", etc.)
Your sample sentence should be "我在我的手机上听音乐" as ChineseHulu.com said.And you actually SHOULD not omit the word "上" in this sentence,or it would be a little bit weird to native Chinese people. 

"在...上" is a preposition phrase.It can be used on representational target like:
在操场上 -- on playground
在沙发上 -- on sofa

And it can be used on abstract target like
在手机上 -- on cell phone
在电脑上 -- on computer
在网络上 -- on internet

Usually we Chinese won't omit "上" if we use this phrase on abstract target or express specific position relation.So these sentence should not omit this word:
我正在手机上玩游戏 -- I'm playing game on cell phone.
我想在电脑上看电影 -- I wanna watch movie on computer.
我通常在网络上聊天 -- I usually chat on internet.
男孩在沙发上跳着 -- The boy is jumping on the sofa.

But if we use this phrase to express the location where something happened,not focusing on the position relation.We can omit this word:
男孩们在操场上玩 or 男孩们在操场玩 are all ok.(Boys are playing on the playground.)

And if you wanna express something happened on the specific location but it's a large area.You MUST omit the word "上" and the phrase thus turn into another single word preposition phrase "在...".
我在上海工作 -- I'm working in Shanghai.
我在苏州旅游 -- I'm traveling in SuZhou.

Apologize for my English.Hope you will get it all... :D