Tiph I didn't realize this was a series, and actually read Princess Spy (which is technically book 5) first. I didn't feel the least bit lost.
Cari This is an old question, but I'll answer anyway. I think you can read the series in any order in that the stories stand on their own and you don't have to know what happened in the previous book for the next to make sense. There will be some spoilers if you read the later books, but I don't think they would be anything you weren't already expecting. That said, you'll enjoy the references to the older stories more if you read them in order. I actually read this one and The Golden Braid at the same time and it was really fun!