> Then try again.

This is very important, as well as, as you say, just doing it.

You (the general you) have a better chance of going on a date if you ask ten people than if you ask only one. You need to be able to handle that not every interaction will be successful, that sometimes people are not interested, and then you just cut it short and move on. Since it's important to get as much practice as possible, it's better to have ten short conversations at the coffee machine, in the elevator, and so on during the day, than one prepared line to say to the person at the front desk as you leave for the day.

Another suggestion to practice talking to people is to approach people who work in clothing stores, cafes, libraries, and so on, and talk to them. They get payed to talk to you, and will make an effort to make the conversation be pleasant for you. You probably won't have the deepest conversations, but the idea is just to experience what it's like to small talk with people. You can either talk about clothes, books, or coffee, or tell them something small about your day and see if they pick it up and asks a follow up questions.

>Unless you suffer from social anxiety

You do it the same way if you suffer from social anxiety. You are just forced to practice coping with anxiety at the same time.

Even if you do have social anxiety practice helps alot. I'd recommend volunteering somewhere that you have to interact with a few new people regularly. It is less overwhelming than most social situations since volunteering is usually task-oriented (if you feel overwhelmed, just focus on the work), and it lets you practice making small talk with other people.

It's better than many in-class alternatives.