Do I have a virus on my phone? A message from an Android app says so I have just received a message from an Android app on my phone saying my phone has been infected with a virus and to click a link to fix the problem. 

I'm not sure I trust this, is it possible to have a virus on Android?
It is possible to have malware on Android, although these usually 'infect' a device through downloading and installing apps from un-reputable and/or warez sites. When installing any app you should review the permissions and not blindly download/install an app simply because it looks ok.

It is possible that the message you received is from a malicious app or an app trying to get you to install malware. You can install a security app such as Lookout or Avast and they will scan your device for issues/malware. Be aware that anti-malware apps such as these can report false positives, and they may not detect all issues so you need to use common sense and ensure you only install apps you trust.

Thanks to t0mm13b for pointers on how to improve this answer.