I would like to know the list of documents I should provide...
Desde que você é casado recentemente, você provavelmente será suspeito de um "casamento de conveniência", mas a evidência de que você mora junto deve superar isso, então inclua algo mostrando que você mora junto.
Fora isso, tudo o que você precisa são seus passaportes e sua certidão de casamento. Se o certificado não estiver em inglês (ou em galês!), Deve ser acompanhado por uma tradução certificada (assim como sua evidência de coabitação).
...and whether my wife should accompany me to the interview (submitting the documents and biometric data collection) or not.
Não é necessário que sua esposa o acompanhe.
How should we prove that she's traveling with me? should I provide flight tickets? or would a cover letter from her addressed to the UK authorities attached with the other documents suffice? and how would such a letter be written and sighned\certified?
Certa vez, preparei uma solicitação de licença familiar da EEA para minha sogra, que planejava usá-la para uma breve visita. Não me lembro se enviámos cópias das reservas de voo, mas suspeito que não o fizemos, porque duvido que tenhamos feito a reserva antes de a autorização ter sido aprovada. Uma simples declaração de que você planeja viajar juntos deve ser suficiente. Não há necessidade de certificá-lo.