The Linux kernel itself treats users are mere numbers. Each user is identified by a unique integer, the user id or uid, because numbers are faster and easier for a computer to process than textual names. A separate database outside the kernel assigns a textual name, the username, to each user id. The database contains additional information as well.
To create a user, you need to add information about the user to the user database, and create a home directory for him. It may also be necessary to educate the user, and set up a suitable initial environment for him.
Most Linux distributions come with a program for creating accounts. There are several such programs available. Two command line alternatives are adduser and useradd; there may be a GUI tool as well. Whatever the program, the result is that there is little if any manual work to be done. Even if the details are many and intricate, these programs make everything seem trivial. However, the section called Creating a user by hand describes how to do it by hand.
The basic user database in a Unix system is the text file, /etc/passwd (called the password file), which lists all valid usernames and their associated information. The file has one line per username, and is divided into seven colon-delimited fields:
Password, in an encrypted form.
Numeric user id.
Numeric group id.
Full name or other description of account.
Login shell (program to run at login).
Any user on the system may read the password file, so that they can, for example, learn the name of another user. This means that the password (the second field) is also available to everyone. The password file encrypts the password, so in theory there is no problem. However, the encryption is breakable, especially if the password is weak (e.g., it is short or it can be found in a dictionary). Therefore it is not a good idea to have the password in the password file.
Many Linux systems have shadow passwords. This is an alternative way of storing the password: the encrypted password is stored in a separate file, /etc/shadow, which only root can read. The /etc/passwd file only contains a special marker in the second field. Any program that needs to verify a user is setuid, and can therefore access the shadow password file. Normal programs, which only use the other fields in the password file, can't get at the password. 
On most systems it doesn't matter what the numeric user and group ids are, but if you use the Network filesystem (NFS), you need to have the same uid and gid on all systems. This is because NFS also identifies users with the numeric uids. If you aren't using NFS, you can let your account creation tool pick them automatically.
If you are using NFS, you'll have to be invent a mechanism for synchronizing account information. One alternative is to the NIS system (see XXX network-admin-guide).
However, you should try to avoid re-using numeric uid's (and textual usernames), because the new owner of the uid (or username) may get access to the old owner's files (or mail, or whatever).
When the home directory for a new user is created, it is initialized with files from the /etc/skel directory. The system administrator can create files in /etc/skel that will provide a nice default environment for users. For example, he might create a /etc/skel/.profile that sets the EDITOR environment variable to some editor that is friendly towards new users.
However, it is usually best to try to keep /etc/skel as small as possible, since it will be next to impossible to update existing users' files. For example, if the name of the friendly editor changes, all existing users would have to edit their .profile. The system administrator could try to do it automatically, with a script, but that is almost certain going to break someone's file.
Whenever possible, it is better to put global configuration into global files, such as /etc/profile. This way it is possible to update it without breaking users' own setups.
To create a new account manually, follow these steps:
Edit /etc/passwd with vipw and add a new line for the new account. Be careful with the syntax. Do not edit directly with an editor! vipw locks the file, so that other commands won't try to update it at the same time. You should make the password field be `*', so that it is impossible to log in.
Similarly, edit /etc/group with vigr, if you need to create a new group as well.
Create the home directory of the user with mkdir.
Copy the files from /etc/skel to the new home directory.
Fix ownerships and permissions with chown and chmod. The -R option is most useful. The correct permissions vary a little from one site to another, but usually the following commands do the right thing:
cd /home/newusername chown -R username.group . chmod -R go=u,go-w . chmod go= .
Set the password with passwd.
After you set the password in the last step, the account will work. You shouldn't set it until everything else has been done, otherwise the user may inadvertently log in while you're still copying the files.
It is sometimes necessary to create dummy accounts  that are not used by people. For example, to set up an anonymous FTP server (so that anyone can download files from it, without having to get an account first), you need to create an account called ftp. In such cases, it is usually not necessary to set the password (last step above). Indeed, it is better not to, so that no-one can use the account, unless they first become root, since root can become any user.
Yes, this means that the password file has all the information about a user except his password. The wonder of development.