Integrating prettyPhoto would be a simple task here. What you will have to deal with to get this feature working is retrieving the information (i.e. the list of posts requested in the selected category) asynchronously (in the background) and would involve using AJAX.
This is what is going to happen:
When a user clicks on a category (e.g. News), WP sends and retrieves data from the server asynchronously (this avoids interference with the display and behavior of the existing page thus no page refresh or flicker). Once the data has been successfully obtained, fire the prettyPhoto plugin and then populate the data there.