Chris242 sez, "With the heightened paranoia– er I mean security in NYC, people with large bags or packages are now being told to submit to random searches in order to use the MTA public transit system. This site has a flyer which tells you what your rights are, and gives advice on how to refuse a search safely."
Again, it is illegal for police to search, detain, or question you just because you refuse a search. But if the police proceed to detain, search, or arrest you despite your wishes — do not physically resist. You may state clearly but non-confrontationally: "Officer, I am not resisting and I do not consent to any searches."