Prepare an invention disclosure
Conduct a boolean search at http://www.patents.ibm.com
Note patent numbers, classes and subclasses
Conduct a full text search at http://www.uspto.gov
Conduct a non-patent literature search
Retain a patent searcher to search "shoes" at USPTO (or do it yourself)
Order a copy of each document, read each carefully
Follow up leads (references, etc.) at least two generations back