The recess you're looking to make is in essence a shallow mortise, much like the type used to hold the stone in a traditional oilstone box.
The most basic way to do this is with a chisel and mallet, after carefully marking out and, ideally, knifing the edges of the recess you want to make (the knife-cut lines help produce clean edges).
It must be said, this is easier said than done and getting a flat, horizontal bottom to the mortise in particular is challenging to do just with a chisel. For this reason the bulk of the material is often taken out by chisel and the final flattening of the bottom is done using a router. This is a hand router, not a modern power tool. Where one is not available the chisel router or "poor-man's router" is a cheap, reasonably effective alternative than can be made in just minutes.
The above method is shown well on this page from Paul Sellers.
If the bottom of the mortise doesn't need to be absolutely featureless a lot of the grunt work can be done by drilling away the excess wood, as mentioned by Paul above. The most-used bit for this purpose these days is a Forstner bit, which will leave a small hole in the centre of an otherwise flat circle as you can see in the link below.
This method is shown in brief on this page of the Norse Woodsmith site.
Note that Forstner bits are best used with a drill press or with a power drill held in a drill stand.
Router
If a modern power router is available it is simplicity itself to cut a recess like this, you can freehand the cut to close to your marked lines and then trim the edges by hand, carefully chopping with a chisel.
Or you can make a template and with a suitable bearing bit in the router you'll cut a near-perfect rectangle through the hole in the template. The corners will naturally be slightly rounded and normally these would be squared up, again using a chisel, but for a phone it may actually be favourable to have rounded corners.
Note: you may want to provide a cutout on one of the straight sides to allow you to lift the phone from the recess. Especially in the case of a very neat fit the phone might be very difficult to remove from a deep recess otherwise!