A lot of ingenuity, and a lot of work.
For some things they can use layers. For example, if a film wants to have a giant castle on a hilltop in the distance, they could paint the castle onto a glass slide and put that right in front of the camera, and then it will look like it is in the background. TVTropes provides [this example](https://static.tvtropes.org/pmwiki/pub/images/tmwwbk_3974.jpg) from The Man Who Would be King in 1975. The actors are filmed on a set or on location, and the painting (at the top) is put over them, and provided it is done well you cannot see the joins. [Here is another example](https://www.thepropgallery.com/media/wysiwyg/glassshot2.jpg) where you can see it being done.
Of course that doesn’t work if the filmed material needs to go in front of the image. For that you add in rotoscoping. A rotoscope is a device [that projects a film onto a painting canvas](https://en.wikipedia.org/wiki/File:US_patent_1242674_figure_3.png), so an artist can paint on it frame by frame. They could go through the film frame by frame and paint over the parts that need to be changed. Part of the point of using a bluescreen is to make this easier – making it really clear to the artist which bits need to be painted over or out.
Compositing was also a thing, whereby if a shot had multiple elements filmed separately (like a main part, a backdrop, a bit in the background) they would be filmed separately, and then the footage would be projected onto a screen with everything else blacked out, and then that would be filmed again. The film wouldn’t pick up the blacked out parts, so wouldn’t develop, and then you’d switch out what you were projecting and film it again, now only exposing the next bits.
Multiple-exposures (where you run your film through the camera several times, exposing different parts each time to layer on effects) can create very complex shots, combining many layers together, but can cause problems with the footage looking a bit washed out.
There’s a great documentary about the early work of ILM somewhere, but I can’t find it. However you might find [this video](https://www.youtube.com/watch?v=jAtULl3ExUo) on the making of the original Star Wars interesting. Star Wars pioneered a bunch of new techniques for effects, and pushed boundaries of what was possible. The original Star Wars has one, repeated, computer-generated sequence in the whole film (the Death Star plans). Everything else was done with practical effects, models, and the techniques listed above. For example [here](https://lumiere-a.akamaihd.net/v1/images/image_e74da0c7.jpeg) is a picture of legendary artist Ralph McQuarrie painting a matte painting for use in ESB (from [here](https://www.starwars.com/news/empire-at-40-5-amazing-matte-paintings-from-star-wars-the-empire-strikes-back)). The black parts are where the live action footage will go [for the final image](https://lumiere-a.akamaihd.net/v1/images/image_4ccf1d80.jpeg). Many of the [epic shots](https://www.reddit.com/r/StarWars/comments/8zol2r/before_the_invention_of_cgi_star_wars_used_matte/) in Star Wars were [made up mostly of paintings](https://www.artofvfx.com/discoveries-from-inside-matte-paintings-unveiled/), [with a bit of actual footage](https://www.starwarsnewsnet.com/2016/04/the-magic-of-the-original-starwars-trilogy-matte-painting-artists.html). Not all of them hold up, but they worked at the time.
Latest Answers