Answer
Every Quick Report automatically gets its own Presentation Object when it's created (findable by querying for the report from the 'Create New Quick Report' screen) — granting a user's Permission Set access to run that report means granting them this specific Presentation Object, not some report-level setting elsewhere. For a SQL-type Quick Report, clicking Publish from the Create New Quick Report screen is the convenient way to do this: it automatically grants the report to every Permission Set that already has access to the underlying database objects the report queries. If the report is already published but a user still can't run it, or if it's not a SQL-type report (so Publish doesn't apply), you'll need to manually grant that report's Presentation Object to the relevant Permission Set from the New Permission Set screen instead.