Any ideas on whether filters should be on the left or right of a table? What about search?
They both narrow down the contents of what's in the table.
I'd put them at the right if you must choose. Unless you really need to filter your data to make sense of it, I'd tuck it out of the left-gutter view most people scan with.
I've also has some really interesting usability sessions that suggest filters/search are confusing for non-techy people whom may rather just scroll. This all depends on the size of your list and target audience, but I highly suggest testing your design against users.
Another thought is to de-emphasize the sort/filters/search until needed and then perhaps on hover making them more prominent.