Oujda is the major city in Eastern Morocco.
Three trains a day arrive from Western Morocco. From Fez, the trip will take about five and a half hours and cost exactly 158/108 Dirhams (First/Second class)
Oujda is accessible from the North via Melilla / Nador as well as from the West via Fes / Taza. Arriving from the South is also possible from Figuig and Bouarfa. Currently, the Algerian border is closed which prevents land travel to/from the East. There are grand taxi's to many destinations including: Taza, Saidia (20 dirhams), Berkane (18 dirhams), Jerada (15 dirhams), Ain Beni Mathar (15 dirhams)
The bus station is located next to the grand taxi station in the South of the city. Many destinations are possible. From Oudja to Taza is roughly 30 dirhams, Oujda to Fes around 60 dirhams.
Boat service is via Nador / Melilla, both around three or four hours away.
There are various decent hotels around the Place du 16 Aout, but two of the best are -Hotel Tlemcen (0536686533), which is attached to a women-friendly patisserie and cafe. 80 dh (around 10 usd) will get you a single room with a hot shower. Friendly staff.
-Hotel Hanna (0536686003) has public hallway showers, but is slightly cheaper.
As all over Morocco, the Hotel Ibis is a safe and well located bet. Always right next to the train station, the Ibis offers wi-fi, hot showers, white sheets, a lovely breakfast buffet, a pool and bar. Even if you aren't staying here, just pop in for an afternoon cocktail poolside (even during Ramadan!)
Another good option in Oujda is the Atlas Spa and Hotel, again, right next to the train station. Swank and brand-new, it's even got a night club (or at least a sign for one).