Paleontological research on predation has been expanding rapidly in scope, methods, and goals. The growing assortment of research strategies and goals has led to increasing differences in sampling strategies, types of data collected, definition of variables, and even reporting style. This methodological overview serves as a starting point for erecting some general methodological guidelines for studying the fossil record of predation. I focus here on trace fossils left by predators in the skeleton of their prey, arguably one of the most powerful sources of direct data on predator-prey interactions available in the fossil record. A critical survey of sampling protocols (data collecting strategy, sieve size, and sample size) and analytical approaches (predation intensity metrics, strategies for evaluating behavioral selectivity of predators, and taphonomic tests) reveals that various approaches can be fruitful depending on logistic circumstances and scientific goals of paleoecological projects. Despite numerous caveats and uncertainties, trace fossils left by predators on skeletons of their prey remain one of the most promising directions of research in paleoecology and evolutionary paleobiology.