does the mere existence of a primary key increase query speed for large data sets? So, I have a table with about 2.4M rows and ~30 columns. There is no unique column within the data. The data is transaction logs from stores where each transaction number is only unique on a per store basis and resets at midnight, but that's besides the point.

As it stands, queries on this table take upwards of one minute and I can't figure out why. I have added indexes on columns that have high selectivity ratio but it hasn't made any difference. So, if I add an auto increment 'id' field for each row, would that speed things up, or are the queries slow because there are so many columns and so much unique data?
Having a primary key per se will not speed up queries. Primary key constraints are usually accompanied by a unique index. If this index matches query predicates or join conditions then those queries are likely to run faster.