I've finished Paul of Dune, the book set between Dune and Dune Messiah. Read halfway through Messiah, to see how the books relate, but there isn't much of a connection.
Paul of Dune is actually two books. Half of it is about a young Paul at the age of 13 and the other half takes place during the first few years after Dune.
I guess the part of Paul at age 13 does something to explain a bit more of the background of Paul, but before Dune there are new books where Paul is 15 and they already do a fine job in doing that, which makes this part utterly redundant.
The other half of the book is more interesting. It does it's best to create an image of the horrors of the Jihad. In Messiah, Paul mentions numbers of planets and people that were destroyed and killed. In Paul of Dune, they try to paint a clearer picture of what this actually means.
Besides that, the book also gives more space to people who only get a brief mention in Dune, just like the prequel stories, which makes sense if you read those.
Summarizing, I think half of the book has value if you read the prequel stories. If you haven't, there is some, but not a lot of value to be had by reading this book. Obviously if you are like me and are going through all 22 Dune books, you really need to read it
