What is the recommended reading order for the Vorkosigan Saga?
Publishing order or is there a better ordering, because I think there is more than one story line?
It's next on my "sagas" list, so I'd like to know where is best to start, and where should I go from there.
You have two options -- either read them in the order of first publication, or in internal chronological order. I think either would work fine.
There's a bibliography here that lists them in order of internal chronology, but also lists the first publication dates if you want to go for publication order instead.
You can skip the linking sections of Borders of Infinity if you can't easily get hold of them -- they're not especially interesting.
In any event, you should read:
Since there's a new novel out now, let me just edit this answer to suggest that you should also read Captain Vorpatril's Alliance after Memory, Komarr and "Labyrinth".
I usually recommend to my friends that they read this series in publication order. There are some strands of storyline that do not follow on directly from each other, however once you get immersed in the books (and you will!) the chronological order of events doesn't seem to matter. You just want to find out what mayhem Miles is going to cause next!
I prefer to follow along with what the author was most interested in exploring as she developed the series. If that means jumping back in time a little to back-fill some context or history, then that suits me just fine. I started reading the Vorkosigan Saga in the early 90s and have spent plenty of time waiting for each of the books to come out, so that may influence my preference for publication order.
I think you'll really enjoy this series, no matter which order you decide to read them in.
Even though there are already three answers, one of which has been accepted, I'd like to give my preferred order. (Also, some books have been published after all these answers.) It is almost internal chronological order, but with a few exceptions that I will justify. First some remarks
1) Though Miles does not appear in "Ethan of Athos", this novel enters at a very precise place in the Saga and is best read exactly there
2) There is some risk of confusion about "Borders of Infinity" that needs clarification
It is at the title of a collection that contains four texts : three novellas called "Mountains of Mourning", "Labyrinth" and "The Borders of Infinity" (note the article "The") respectively, plus some "linking pages" often also called "Borders of Infinity". These linking pages have only be published in this collection, while all three novellas can be found in various omnibus editions.
The novel "Falling Free" is in my opinion one of the richest ones in the Saga, because of the deep humanity of some characters. It would be a great loss not to read it at all. But though chronologically it is the first one, I do not recommend to read it first. I think one should get acquainted with the world of Miles Vorkosigan first.
So skipping for the time being "Falling Free" proceed in chronological order starting from the second one. So:
Shards of Honor
Barrayar
Warrior's Apprentice
then the novella "Mountains of Mourning"; if you have it only in the collection "Borders of Infinity", skip the "linking pages" that precede it and read it alone; if you have it in another edition, well, just read it
The Vor Game
Cetaganda
Ethan of Athos (yes, precisely here)
At this point, before reading "Labyrinth, (or somewhat earlier,) would be a good time to read "Falling Free", but it is not yet necessary
If you do not have the collection "Borders of Infinity", read "Labyrinth" and then the novella "The Borders of Infinity", both of which appear in other places (omnibuses, for instance)
If you do have the collection "Borders of Infinity" then proceed to read it in order, first set of linking pages, skipping "Mountains of Mourning" that you have read long before (or rereading it, it is so beautiful !), proceeding to the next set of linking pages, then "Labyrinth", third set of linking pages, then the novella "The Borders of Infinity" and final set of linking pages.
Even though the events of the linking pages take place after those of "Brothers in Arms" they don't give any spoiler and are best read before it. This is the second exception to the chronological order. Then resume it
Brothers in Arms
Mirror Dance
Memory
Komarr
A Civil Campaign
Winterfair Gifts
If you have not read "Falling Free" before, now it really is necessary to read it, otherwise you won't be able to fully enjoy your next read
Diplomatic Immunity
Captain's Vorpatril Alliance
Cryoburn (which does not give any spoilers to Captain's Vorpatril Alliance - if you want you can read it first, as it was published first, it really does not matter)
Flowers of Vashnoi
Gentleman Jole and the Red Queen
If you can get hold of the collection "Dreamweaver Dilemma", know that the titular novella in the collection (not published anywhere else, to my knowledge) is also in the same Universe, and takes place even before "Falling Free". But it can be read at any time, the links with the remainder of the Saga are very weak. The only "plus" you get from it is an understanding of why Dubauer is such a common Betan name, as ruakh has already remarked in a comment to Is there any significance to the reuse of the name "Dubauer" in Shards of Honor and Diplomatic Immunity?
Also, if you cannot get hold of the collection "Borders of Infinity", just reading "Labyrinth" and the novella "The Borders of Infinity" will be quite OK, you won't miss much from the linking pages. There is just one little thing, there is one short discussion in the "linking pages" which is alluded to in a later book, and of course this allusion becomes incomprehensible. But most readers will just think they did read about it and forgot and won't worry about it. Only very few will try and check in the entire Saga to see where this comes from, and not find it !
Start with The Warrior’s Apprentice - This book starts the main series of Miles Vorkosigan. Everything you need to know is either explained or assumed.
The Vor Game - There is a book (novella), which fits between the Warrior’s Apprentice and The Vor Game. I have this novella included in another book which is actually a set of three novellas given as a report to Miles’ C.O.
Cetaganda - This book follows The Vor Game directly in the series.
Brothers in Arms - If you’ve made it this far in the series you’re probably hooked.
The Borders of Infinity - This is the collection of three novellas mentioned earlier, these novellas occurred at different points in the timeline of the series, but none of them occur any time further on in the series, so no spoilers. I consider these novellas to be integral to the whole series.
Mirror Dance - The timeline of the series picks back up here.
Memory - Continuation of the series, this book is something of an evolution for Miles.
Komarr - Continuation of the series.
A Civil Campaign - Continuation of the series.
Winterfair Gifts - Novella
Diplomatic Immunity - Continuation of the series.
Captain Vorpatril’s Alliance - This book does not actually follow Miles as the main character, but instead follows his cousin Ivan. Don’t miss this one; it’s really amusing.
Cryoburn - The last book in the main series. If you've liked it all so far the other books give context and are generally enjoyable.
Falling Free/Shards of Honor/Barrayar - These three books are something of prequels to the main series. I suggest that if you read these at all, you read them after you read the main series. They are interesting but more of a footnote. Also if you do read these, note that they were written by the author after the main series.
Ethan of Athos - This book falls in-between Cetaganda and Brothers in Arms in the timeline. This book does not feature Miles, but does feature Elli Quinn. This is another book that should only be read after the main series.
