Your question is a bit confusing. DO you want something to happen when user selects contact in the lookup? (what if he selects one, then another one, then maybe selects 1st one again?)... I think some problematic scenarios sit in this area so maybe think again what you want to achieve... And if that's really it - Visualforce Case creation page (don't expect it to work when Case comes from outside like Web-to-Case, Email-to-Case, customer portal...)
If it has to happen on Case save... I don't think you can make cross-object workflows between Case and Contact and besides picklist updates in workflows are annoying (select previous/next value on picklist... wow, awesome, thx SF).
P.S. It's not exactly "Parent" ;) If you'd have a master-detail relation between the two you could cheat by either making it a rollup summary or make a workflow on Contact "count of cases changed -> do something". Alas standard object can't be a "detail".
EDIT: Or maybe you're on the Case viewing page? Then you're one click away from editing the contact (hover over the link, balloon pops up, )... If you really really need to do it from detail page - embed a VF page in the layout:
<apex:page standardController="Case" extension="myclass">
and in the Controller extension query for contact etc.