assuming apache server you could use a configuration directive with regular expression matching:
[httpd.apache.org...]

So if I put a .htaccess file in the /olddir/gallery/ directory and then in the .htaccess file put:
Redirect / ../../newdir/gallery/
I could then go to my browser and type www.mysite.com/olddir/gallery/dispimg.php?id=723 and I would find myself on the page www.mysite.com/newdir/gallery/dispimg.php?id=723 once it loads?

Yes, although the server-relative form should be used for the new partial URL-path:

Redirect / [b]/n[/b]ewdir/gallery/

Also, if this move is permanent, and you want the search engines to update their results to show the new URLs, then you should indicate a permanent redirect:

RedirectPermanent / /newdir/gallery/

-or-

Redirect 301 / /newdir/gallery/

Jim

[edited by: jdMorgan at 9:30 pm (utc) on Nov. 20, 2006]

I would like to add my own question here: If I'd like to redirect all images in "imagen" directory to "files" firectory, would the rule be?:

Redirect 301 /imagen/ /files/

assuming I want, for example:

http://www.mydomain.com/imagen/picture.gif

changed to

http://www.mydomain.com/files/picture.gif/

Is that all right?

Thank you so much :)

Redirect 301 /imagen/ /files/

That would be Redirect 301 /imagen/ [yourdomain.com...]

Meaning you need the full path to the new location.