How are fiction books such as novels sorted on the shelves at Japanese bookshops? Kana order seems to play a small part but not the whole part.
(I'm not asking about nonfiction books since those are ordered by category and are much easier to find)
From what I've observed, it varies from shop to shop:
Also, 文庫 and 新書 are placed in separate bookshelves on their own.
As for libraries, most of them follow the NDC classification system. NDC stands for Nippon Decimal Classification.
If you go to a library, you'll see that books are labelled with NDC classification number (分類番号 [ぶんるいばんごう]), a letter or two denoting the Kana to be used for further ordering1 (図書記号 [としょきごう] / 著者記号 [ちょしゃきごう]) and an optional series number (巻冊記号 [かんさつきごう]). These numbers are called 請求記号 [せいきゅうきごう] as a set and is used for ordering books and tracking down a book to a specific location in the library2 3:
+-------+ | 810.4 | - 分類番号 + +-------+ | | イ | - 図書記号/著者記号 +-> 請求記号 +-------+ | | 2 | - 巻冊記号 + +-------+
Here's how it looks like (notice the small white labels at the bottom of the spine):
For fiction books, they fall under the main class of 9, and further classified like:
9 - Literature 900 - Literature 910 - Japanese Literature 911 - Poetry 912 - Plays 913 - Novels ... 920 - Chinese Literature ...
Again, 文庫 and 新書 will be in separate bookshelves in libraries too, and can be ordered by library → by series number instead of NDC.
 Usually the first letter of the primary author's surname, or the book title when there are a lot of authors.
 Some libraries may have an internal tracking number of their own, in addition to / in place of NDC, especially the small, private or academic ones.
 This sounds all neat and ordered, but 請求記号 isn't portable across different libraries, because they have different ideas about how to format it and what to use for 図書記号.
I haven't been to a Japanese library yet, but judging from the book shops I have been to so far, fiction and such have been sorted by publishing house (such as Kadokawa or DC Comics).