A Celeron 500MHz is pretty much borderline- it should be able to play back most DVD's with softweare decoding perfectly adequately but it may become a bit choppy in some scenes in excessively 'active' movies.
In general you should look towards a Celeron/PII 300MHz at a minimum, while 400-500MHz should adequately decode the vast majority of DVD's perfectly fine.
600MHz Celeron/PIII would be ideal, at that point the processor alone would be up to the task of decoding DVD movies quite fine.
If your on a budget then the Celeron 500MHz should do pretty well, but if you want an assurance then I'd suggest you look for a cheap ATi Rage 128 card.
Rage 128's are extremely cheap and easy to get and have exceptional hardware DVD playback capabilities.
Don't expect to be able to do ANYTHING else while watching the DVD however. Even modern PC's can slow down significantly if attempting to perform any intensive tasks while playing back the DVD.