Hellos,
"How to select a stagename?" Your stagename is up to you o.O Some utaite just spontaneously choose their name because they see something nearby when they create their account XD but it can just as well have some deeper meaning to yourself, or maybe even an alternation of your real name.
"Is permission needed to cover Vocaloid or Anime songs?" As for VOCALOID songs, normally not. Producer's normally put off vocals of their songs in their video description. However with anime songs, there might be some copyright issues. If you are going to cover songs on YouTube, I'd be extra careful with that XD. However I think some anime are alright, and you might also want to change the pitch to avoid those issues.
"I noticed that Utaites have their own illustrated characters. How do I get one? Is it possible to get someone to help me with illustration?" Not all Utaite have their own illustrated depiction. But I guess those who have, are often friends with the illustrator, unless the illustration is a fandepiction. However when you first started, I don't think you need illustrations or illustrated videos. When people start noticing you, they'll come over the time (Though you can also ask your illustrator friends I guess.)
"How do I cover songs? Other than recording your singing, what else do I need to do?" You'll need to mix, encode and master your videos. (Or find someone else, who can help you) "Editing" might just refer to mixing.
For more information, read this thread and this.