Wikimedia Commons items should have their licence data attached, e.g.

http://commons.wikimedia.org/wiki/Category:Public_domain

Though I'm not sure how you can search just that subset.

Found it, add +incategory:"Public Domain" to the search, as in this example searching for "cats":

https://commons.wikimedia.org/w/index.php?title=Special%3ASe...

Example result (interestingly tagged as both public domain and CC):

"Two cats, dressed as humans, holding rope, which doll appears to be skipping"

https://commons.wikimedia.org/wiki/File:Two_cats,_dressed_as...

Though, from the dearth of results that may not be searching sub-categories.