@Rhiannehibbs You basically need a Phone System license and a Calling Plan license for each user. Depending on the country/region that your Office365 tenant is in, you might be able to get a Teams Phone with Calling Plan license (previously named Business Voice), which is essentially a bundle of the two aforementioned licenses.
Once you have these licenses in place and assigned to your users, this will allow you to request Phone Numbers directly from Microsoft in the Teams admin panel, which you can then assign to each user. (If the Teams Admin panel shows a message that numbers are not currently available, click on the link it will show to open a case with Microsoft support. They will tell ask you a few questions to get the numbers procured.)
Please note that there are two types of Calling Plan licenses, "Domestic" and "Domestic and International". If you get the Teams Phone with Calling Plan license, that only includes a Domestic Calling Plan.
There is another option also available to add the ability to daily out to international numbers if you already have a Domestic Calling Plan. It is called "Communication Credits" license. The license itself is free and can be assigned to any user, but you will be asked to "fill up" the credits with a certain amount of money that you choose. Once those credits are used up, you have to fill up again, or set it to auto-recharge.
Just FYI, the Calling Plans have a certain amount of minutes that are pooled between all users who have the same license assigned. The Communication Credits can also be used compensate those minutes if the pool of minutes for the calling plans have been exceeded (whether the calls are domestic or international).
Some people find the monthly fee for Calling Plans provided by Microsoft to be a bit expensive, particularly if the amount of calls placed by users are limited. In that case, it might be prudent to seek out a phone provider that is certified to provide "Operator Connect" services for Microsoft 365. That provider will provide you with the phone numbers and PSTN connectivity, but you still have to provide Phone System licenses to each user. There will be an initial setup fee from the provider, but the benefit is that domestic and international call rates are usually cheaper overall, and sound quality may be improved (depending on your location).
