Maintain unique user name in Test methods?

This is a common issue as usernames are shared across instances, but not across environments (production/sandbox). In order to resolve this, I recommend you build your username dynamically i.e make use of prefixing with OrgId + Timestamp.

String orgId = UserInfo.getOrganizationId();
String dateString = String.valueof(Datetime.now()).replace(' ','').replace(':','').replace('-','');
String uniqueName = orgId + dateString;

Having the unique name as your username prefix will prevent duplications on an insert call.

Update

The use of each replace method may confuse you therefore I offer another solution to generate the timestamp portion of the dynamic prefix. Both will work, your preference over which String to append.

String dateString = String.valueof(Datetime.now().getTime());

It would be more usable to have a reusable utility method.

I used to follow an example, following code from the documentation is much closer to it - How to resolve DUPLICATE_USERNAME error returned while performing a deployment

public static User createTestUser(Id roleId, Id profID, String fName, String lName) {
    String orgId = UserInfo.getOrganizationId();
    String dateString = 
        String.valueof(Datetime.now()).replace(' ','').replace(':','').replace('-','');
    Integer randomInt = Integer.valueOf(math.rint(math.random()*1000000));
    String uniqueName = orgId + dateString + randomInt;
    User tuser = new User(  firstname = fName,
                            lastName = lName,
                            email = uniqueName + '@test' + orgId + '.org',
                            Username = uniqueName + '@test' + orgId + '.org',
                            EmailEncodingKey = 'ISO-8859-1',
                            Alias = uniqueName.substring(18, 23),
                            TimeZoneSidKey = 'America/Los_Angeles',
                            LocaleSidKey = 'en_US',
                            LanguageLocaleKey = 'en_US',
                            ProfileId = profId,
                            UserRoleId = roleId);
    return tuser;
}

Don't use "test.com" or "contoso.com" or some generic domain like that. Almost everyone at some point has used those addresses because they figure that they shouldn't be cluttering up their own domain with useless usernames. That's really a bad practice, because it does cause complications. Use your own domain name, just with some crazy variation that wouldn't normally be used. For example, if I worked for Microsoft, I'd probably use a username like "[email protected]." At my current organization, I use our domain name for test users, because I can be fairly certain nobody else is using it. In addition, I also generate the username randomly so parallel tests don't interfere with each other. I always stick to using our own domain name, though, so I don't collide with other orgs.