According to Wikipedia, a $k$-core in a graph is a connected subgraph in which every vertex has degree at least $k$. Your set $S_k$ is the union of the vertex sets of all of the $k$-cores of the graph.
(However, I think that people often use the word $k$-core to refer to the subgraph induced by the set $S_k$ that you have defined; at least, that is how I would use the word $k$-core).
Similar to what Gerhard suggested, you can find the set $S_k$ by initialising $S_k:=V(G)$ and then deleting every vertex of degree less than $k$ in the subgraph induced by $S_k$ until either $S_k=\emptyset$ or there are no such vertices left.
With regards to $k$-cores in random graphs, one natural place to start might be the paper Size and connectivity of the $k$-core of a random graph by Tomasz Łuczak.