I have been trying to play Monkey Island 4. From what I understand, I must apply an update to the game files. But how do I do it? I have downloaded MonkeyUpdate.exe, is that the correct one?
When I try to install the update, it says:
Escape From Monkey Island not found. Please reinstall the game from the original CD-ROM and try again.

I didn't actually install the game, I just copied the data files to a Monkey4 directory under the ResidualVM installation:
c:\residualvm\Monkey4\Movies
c:\residualvm\Monkey4\Textures
c:\residualvm\Monkey4\Textures\mego
c:\residualvm\Monkey4\Textures\spago

From where should I apply the update? I tried installing the game from the CDs, but it doesn't run in a 64 bit OS. So now I am a bit lost.

You do not need to apply/install it.
Simply place the exe file in the game folder, and ResidualVM will read any needed info straight out of it.

That is all.