What are Laplacian scores and how do they effect feature selection?
As @Spacedman said, the paper provides a very clear explanation of the algorithm on page 2.

If you're a little less comfortable with the math of the notation, here's the intuition/explanation in words.


Make a k-nearest neighbor's graph. That is, for each observation, define an edge in the Graph for that observation if another observation is one of its k-nearest neighbor's. If you're using a supervised algorithm you can define an edge if they share the same label.
If any two nodes (observations) are connected, define a weight matrix S measuring the similarity between those two nodes (using some distance measure). 
For each feature define the Laplacian graph.
Compute the Laplacian score based on their equation.


Intuitively, you're using KNNs to define a network graph and assessing how similar the features are according to your distance metric. This is just as good of a measure of feature importance as any other but will also has its pitfalls, just like all of the others.