Buses run to Tacna from Lima (20 - 22 hours), with the more luxurious companies (Cruz del Sur, Tepsa, etc) leaving from Gran Terminal Terrestre and the cheaper companies leaving from their own terminals along 28 Julio & La Victoria. Cheapest ticket with Tepsa cost S./107pp, left Gran Terminal Terrestre at 1pm, and took 22 hours (Oct 2015). These buses also stop at points south along the coast, including Nazca (12 hours), as well as Arequipa (6 hours, 20 to 50 soles). Check more information about bus schedules at AndesTransit.
Busses from Arica cost around 2.000 Clp (12 soles) as of January 2019. The trip will take around 1.5 to 2h, crossing the border is generally easy and unproblematic. Alternatively you can tale the train from Arica which runs twice a day (departing around 9 am and 7 pm) for 3800 Clp (2019).
Munchener, Reasonable prices and a selection of artesanal ales. A porter from England was 9 soles for 500ml
Hotel Torresur, $21 for a matrimonial, en suite, breakfast included (bread), wifi, clean and reasonable. But a bit out of the way.
Caretur Tacna (Cámara Regional de Turismo) www.careturtacna.com
To continue onwards in Chile, walk to the domestic terminal right next to the international terminal and buy a bus ticket from there. Food, money exchange, baggage deposit and bathrooms are available inside. Update November 2018 -- if you take a bus from Tacna to Arica, but you fly into Tacna airport, you need to first take a taxi from the airport to international bus terminal located in town as above. While touts demand 20 or 30 sol, insist on 10 -- someone will agree, few passengers, many drivers; it takes about 10 minutes to get to the bus terminal. Pay that tax, walk diagonally across the building to buses; you will give your passport and they log your information into a cumulative sheet that is then provided to immigration on the border -- Peru / Chile windows are side by side. You get your passport back at the border and you present it to immigration. They collect fare on buses. Very straightforward. When you arrive to Arica, it is possible to change money in domestic bus terminal after about 8:30 AM. No issue getting a seat on a bus travelling south, but some lines accept only cash. There are many more options at the bus terminal than online. The bus terminal seemed safe even at 11 PM -- there was a security guy.
Another option to get to Arica is to take the train which runs twice a day. Book in advance, because the train is small and has only few seats. The price is 3800 pesos (2019).