The best way to deal with relations
You need to get the data structure right, then everything will fall in place using Views. 

Apart from city, cinema and movie content types, I'd suggest creating a session content type, too, which would link a movie with cinema, adding the time and hall number information. To maintain relationships between individual chunks of data, you want to use the CCK's node reference module (it is part of D7).

Roughly, you'd go with content types like so:

city (name)
cinema (name, city_ref, hall_count)
movie (name, description, picture, rating)
session (movie_ref, cinema_ref, hall_number, date_time)


It always depends on your requirements, but in this particular case I'd recommend using a separate content type for cinemas instead of taxonomy. Each cinema's node would serve information about the cinema, number of halls, and it would also reference the city it's located in and would be referenced by the screening nodes.

On the other hand if you have no other information about a city other than it's name, it should be safe to set it up as taxonomy.

To make it all work together, i.e. display listing pages, or allow users to search for movies and session times, you'll have to pick up the Views module.

Implementation of a "movie description and all it's showtimes" page would be the movie node page with a view attached (via Views Attach for D6 or EVA for D7) that would list show times for the movie passed as node ID from URL.

For the "cinema timetable with movie names and times", you'd do the same thing, but since you're displaying information about multiple movies, you would also use Views relationship (session -> movie_ref) to fetch in the movie nodes to be able to use their names as a views field.