Most Americans are uncomfortable with the fact that Internet search engines record their users’ queries, according to a survey released Wednesday that examined perceptions about federal authorities’ demands for such records.

Search engine companies recently sparked the debate by responding differently to the Justice Department’s subpoena for records on what their users had been looking up.