In order to add a new client, you need to go to Clients → Add Client and enter the client details.
Admins and users who can create projects are the only ones that can add new clients.
NOTE: You can associate a project with a client, but this is not mandatory. If you have internal projects, you can add your company as a client for your internal projects.