The tickets on all long-distance trains in Russia are tied to a specific seat (or, well, bunk in a sleeping car); this is similar to what is called "mandatory seat reservation" in Europe. Therefore the trains can be sold out.
However, on ordinary trains (not special free-of-charge trains for World Cup fans) there are different classes of tickets, and usually the most expensive are available up to the very departure.
You can look up and buy tickets on the official site of Russial railways. Note that the interface can be sometimes difficult to comprehend (in particular due to poor English translation sometimes). You need to select the departure and arrival station from the drop-down lists that appear as you start typing. Select "Volgograd 1" or "Volgograd 2" for the departure station (this apparently are two different stations in the city; some trains may call at one station and some trains may call at another; some may call at both; so you might need to try both). Select "Nijnii Novgorod Moskov" for the arrival station ("Moskov[sky]" is the name of a particular station in Nizhny, this is the only station used for long-distance trains).
UFS Online is an official ticket-selling agency of Russian Railways and probably you will find their site easier to understand. Apparently they allow to look for trains from any Volgograd station at once (i.e. not specifying whether you need Volgograd 1 or Volgograd 2). However, they charge additional fee (several hunderds of rubles, I guess).
There is a direct train service that apparently runs every second day. I can see tickets available for June 19 and 21 and 23, for about 2500—3000 rubles, the ride takes 1 day 3 hours. Also, you can find a lot of options with a change in Moscow (but you will have to buy two separate tickets and most probably change the stations in Moscow).
Note that the direct train seems to be not a very comfortable one with old rolling stock ("Service class: 2Л" is the most basic one); the price also suggest this (3000 rubles for a 2-nd class ticket for more that a day trip is really cheap). For example, you might find that the toilets are closed during the (long) stops.
Note that also there are direct flights between the two cities by Utair and Aeroflot, and surely there are plenty of flights via Moscow. They are somewhat more expensive (Aeroflot seems to start from 6000 rub), but much faster.