It is no secret that the name of a game should be unique, easy to remember and reproduce, and also should be short. Ideally, it must reflect the game's idea and have an emotional tone very close to the game's mood. This is your brand, so pay the maximum attention to it.
The name can be based on the plot of your game and include either the description of the game's situation or one of the character's names. It can include some hints on the game's genre or mechanics. Try not to overthink the name and avoid including various semantic games and rebuses in it (in exceptional cases they are really genius). Try to recall the Tom Hanks movie, That thing you do! (1996), in which there was a pop band that called itself The Oneders, thinking that the audience would know to pronounce it "one-ders". The word was supposed to be wonders, but they thought it was smarter to spell it this way. Of course, they were wrong because all around called them "oh-need-ers".
It is highly possible that all the single-word names will already be taken, but do not get discouraged, because with a double-worded name you have more chances. But try to avoid too-long names. In iTunes Connect Developer Guide, in the chapter Adding New Apps, there is a phrase:
"The app name cannot be longer than 255 bytes and can be no fewer than two characters."
So, 255 bytes is the maximum length of the app name, but most people do not reach that limit. Practically, there is a more important point: the length of a text label situated below the application icon. Subjectively, the title looks more attractive and professional if it can be written in a single row of text (different subtitles and functional words can fill in the second row). The following screenshot illustrates various text labels. Some of them have only one row of text, some use two, and the last one fills up all the lines and features some symbols truncated:
The length of the text label is measured in pixels, not in text characters. Usually it is equal to dozens of letters. If your name includes narrow letters such as I, L, and J, there will be many more characters in the text label (for example, up to 16). In contradistinction, the words with wide letters W, O, and so on would take more space. So, always experiment with various words. The hyphenation algorithm used on the App Store works with phrases, so it breaks down not words into letters, but phrases into single words, this is why it is sometimes difficult to write a few long words in a single line. If the name is longer than both text rows, the name will be truncated, the system will replace some letters with an ellipsis. iOS in its turn writes names of applications in one line without hyphenation. So, if a text label is long, it has been broken off and has got the ellipsis, which looks very unattractive, like a torn dress. That is why some developers try to use abbreviation or short forms of their titles on devices. For example, PopCap had to use a shorter alias for Plants vs. Zombies 2, which was overly long for iOS, so PvZ 2 was used instead. When talking about names for mobile games, the old phrase "less is more" rings true.
Having invented the name, try to check its availability. This can be done by searching for it on Google, App Store, and other popular locations. It is worth checking whether or not your chosen name is already a trademark. Otherwise, if the title (or some of its parts—for example, the term "Tower Defense" is copyrighted) and belongs to somebody, but your published game used it widely, there can be some unpleasant consequences: because of trademark disputes, the application can be removed from App Store. There was a buzz about the puzzle game Edge by Mobigame; despite being a critically acclaimed product, it was removed from App Store a few times because of disputes about the word "Edge" used in the title (http://en.wikipedia.org/wiki/Edge_by_Mobigame).
The availability of a name can be checked via various official online services, for instance, United States Patent and Trademark Office (USPTO) has Trademark Electronic Search System (TESS) on their website http://www.uspto.gov/trademarks/index.jsp. There is a similar system in the United Kingdom, the Intellectual Property Office has search trademarks option on their website http://www.ipo.gov.uk/types/tm.htm. There is also The Office for Harmonization in the Internal Market, which is the registry of trademarks within the European Union. It has a database search on its website too (http://oami.europa.eu/ows/rw/pages/QPLUS/databases/searchCTM.en.do).
You must be prepared for the name to already be taken (there are thousands of games in the world, so many good-looking titles are already used), so always have some alternatives. It is always better to check the name before development, because the name can be introduced in the plot and the story.
If your name is free and you can use, it is necessary to secure it; you must register the Internet domain name (it is better to use the .com address) and create topical accounts on communities on social networking sites. For example, you will need a Facebook page for your game, a YouTube page, a Twitter account, a Tumblr page, and so on. Of course, the main marketplace is the App Store (Google Play, BlackBerry World, and so on too if the game is ported on new platforms); nevertheless, an official website and social media should not be underestimated; they may help the game with additional marketing. On the website, we can embed some YouTube videos: a trailer or some gameplay demonstrations, some descriptions, and examples of artwork, and a blog can be made of developer diaries. Many players like such information very much, especially if they are familiar with previous titles of a developer. Additionally, some extra plot information can be placed on the website to expand the world of the game; this can include image maps of the in-game universe, special web episodes, simple comics, or short novels related to the title. Another good idea is to have small goodies for the audience: wallpapers (both for handheld devices and desktop computers), some images that can be printed as stickers, and some papercraft maybe.
The main idea is to convince current and potential players that you love them a lot. The design of the official page should be simple and clean, concentrating all attention to a central table with the game logo, video, and some text description; an App Store Badge with a link to iTunes is mandatory. The social networking sites are much easier to manage; they only require you to update status periodically to keep the audience up. Various likeable screenshots and illustrations from the game are good. To properly decorate the account, you only need to choose proper avatars and title backgrounds.