It will depend on which media player you're using, but lots of the
Linux media players can be controlled by the command line. xmms for
example had lots of options for controlling a currnetly running xmms
process, including changing the current playlist.

I run around 40 web kiosks using Mozilla. I've set GDM to auto log in
a non privliged user, and given that user a simple .xsession file:

#!/bin/sh
export PRINTER=`cat ~/.printer`
exec /usr/bin/xscreensaver -no-splash &
exec /usr/bin/sawfish &
exec /home/shopfloor/.xosdclock.sh &
exec /usr/local/mozilla/mozilla -splash

As Mozilla doesn't go into the background, the .xsession doesn't end
until the Mozilla process exits. When that happens, X is restet, the
user gets auto logged in, and the .xsession is run again. Keeps the
user from getting into trouble. Sawfish is running in the background
because Mozilla really didn't want to deal with no window manager, but
sawfish doesn't manage Mozilla windows (but it does manage pop ups
like printer dialogs and help windows).

Simply changing the contents of a playlist while your media player is
running won't work. The player would have to monitor the playlist for
changes, which most don't.

If you wanted to keep all the video displays in sync, I'd look at a
video streaming type solution. Then you would just have to have your
clients tune in your streaming server, and you'd have total instant
control over the content displayed.

-- 
Andrew S. Zbikowski | http://andy.zibnet.us
SELECT * FROM users WHERE clue >0;
0 rows returned