Nekovalkyrja usually have a Japanese (or, less commonly) a Norse name.

Examples:

• Takahashi Shinobu (surname followed by name; most common)
• Brynhildr Shuichi (Norse first name followed by surname)
• Alfhildr Ymirsdottir (same as above, but with a Norse surname)

These random name generators are great for Yamataians, Jiyuuians and Nekovalkyrja):

• Random Nekovalkyrja Generator (includes names)
• Japanese Girl Name Generator (external link)

I always figured they were from a pool of approved names each factory had. The purpose of the names were to give small groups of nekos a social structure (family), particularly ones going to the same assignment.

In the old days, nekos were always created and deployed in groups of 3, and so the three shared a surname.

One thing I was also thinking was that nekos might be drawing their last names from scientists whom worked on either creating the nekovalkyrja species in the first place or the slew of personnel whom were in charge of creating the 'units' themselves.

Alternatively, they might have surnames based on the ship they were born from if they were sprites (and lets face it, a large part of the neko population starts out as sprites). For example, Wes compared all the sprites he had to flower blossoms in some ways and they could very well have official names like Cherry Sakura and Blueberry Sakura if there was need to add it.

I know the above is unofficially what I was betting on for Miharu's sprites; Mara Miharu, Hinoto Hoshi, Ichigo Miharu, Nimura Miharu, etc… it might seem repetitive on the same ship (which could be why it's left unmentioned, but once the sprite 'outgrows' her birthship then she gets a handy surname to use. Typically, ex-sprites take their creator ship's name as their surname; for example, “Sakura Cherry.”

Nekos are given the power of language from birth. They can form names based on whatever they so please, and could probably change it anyway when they wanted to. Name changes are available if desired. Many nekos choose their own names.

Nekos are born in small groups with identical last names: i.e. out of a production of 250 nekos there will be ~60 different family units.

The names are usually chosen from a pool of pre-approved last names, which is unique to each installation. Sometimes a techie (their creator) can give them his/her last name as well. Or possibly their own last names are included in said pool.

Like modern times, it isn't required that the neko keep the assigned last name, and it is capable of being changed.