I've lost my phone and in order to access iCloud I need my Apple ID however I don't remember the one that is linked to my iPhone. What can I do to find this out?
There doesn't seem to be any easy way to do this.
To do it by trial and error, you can go to the iCloud web-site and login with each of your Apple IDs and try the "Find my iPhone" feature to locate it and/or send a message/tone to it.
If you have any other iOS devices with a similar setup, you can check on them as well.
There's isn't really a way. I guess you could check iTunes or iCloud settings on your computer to see what account it used?
As well, Apple's iForgot has a tool that will help you find out which one of your email addresses is an Apple ID.