Faits:
A. D._, né en 1966, travaillait comme ouvrier au service de la société X._. Le 26 février 2000, il a été victime d'un accident de ski entraînant une lésion au genou gauche. Depuis cette date, il n'a plus exercé d'activité pour son employeur et résilié ses rapports de travail au 30 juin 2000. Les suites de l'accident ont été prises en charge par la Caisse nationale suisse d'assurances (CNA), qui a alloué à D._ une rente fondée sur un taux d'invalidité de 13% à partir du 1er juin 2005 (décision du 4 janvier 2007 et décision sur opposition du 21 février suivant).
Entre-temps, le 11 avril 2001, D._ a déposé une demande de prestations de l'assurance-invalidité. Après avoir effectué plusieurs stages d'évaluation et d'orientation, il a suivi une formation pratique de deux ans dans le montage d'appareils électroniques et des cours d'informatique à la charge de l'assurance-invalidité. Au terme de ces mesures, l'Office de l'assurance-invalidité pour le canton de Vaud (ci-après: l'office AI) a complété l'instruction sur le plan économique et médical, en requérant notamment l'avis du docteur S._, spécialiste en neurologie. Dans un projet de décision du 10 novembre 2006, puis par décision du 2 novembre 2007, l'office AI a nié le droit de l'assuré à une rente d'invalidité, au motif qu'il ne présentait pas un degré d'invalidité (fixé à 11%) suffisant pour ouvrir le droit à cette prestation.
B. L'assuré a déféré la décision sur opposition du 2 novembre 2007 au Tribunal des assurances du canton de Vaud (depuis le 1er janvier 2009, Cour des assurances sociales du Tribunal cantonal), qui l'a débouté par jugement du 18 novembre 2008.
C. D._ interjette un recours en matière de droit public contre ce jugement, dont il demande l'annulation. Sous suite de dépens, il conclut au renvoi de la cause à l'office AI pour qu'il complète l'instruction sur le plan médical.
L'office AI conclut implicitement au rejet du recours, tandis que l'Office fédéral des assurances sociales a renoncé à se déterminer.

Considérant en droit:
1. Le recours en matière de droit public (<ref-law>) peut être formé pour violation du droit selon l'art. 95 sv. LTF. Le Tribunal fédéral statue sur la base des faits établis par l'autorité précédente (<ref-law>) et peut rectifier ou compléter d'office les constatations de celle-ci si les faits ont été établis de façon manifestement inexacte ou en violation du droit au sens de l'<ref-law> (<ref-law>). En ce qui concerne, en particulier, l'évaluation de l'invalidité dans le domaine de l'assurance-invalidité, les constatations de l'autorité précédente sur l'atteinte à la santé, la capacité de travail de l'assuré et l'exigibilité relèvent d'une question de fait et ne peuvent être contrôlées que sous un angle restreint (<ref-ruling> consid. 3.2 p. 398).
2. Le litige porte sur le droit du recourant à une rente d'invalidité. A cet égard, le jugement entrepris expose correctement les normes légales sur la notion d'invalidité et son évaluation (dans leur teneur en vigueur jusqu'au 31 décembre 2003, puis du 1er janvier 2004 au 31 décembre 2007 [4ème révision de la LAI], applicable en l'espèce [<ref-ruling> consid. 1 p. 11 et les arrêts cités]). Il suffit d'y renvoyer.
3. 3.1 La juridiction cantonale a constaté qu'en plus des séquelles de l'accident du 26 février 2000 au niveau du genou droit, le recourant souffrait d'une atteinte à la santé étrangère à cet événement, à savoir d'un syndrome des apnées du sommeil avec un syndrome des jambes sans repos. Dans ce contexte, elle a retenu en renvoyant à l'avis du docteur S._ qu'il appartenait à l'assuré, en vertu de son obligation de réduire le dommage selon l'<ref-law>, de suivre un traitement adéquat pour améliorer la situation jusqu'à ce que l'atteinte n'affecte plus sa capacité de manière quantifiable. Cette affection n'était dès lors pas invalidante au sens de la loi. En ce qui concerne la nature et la gravité de l'atteinte au genou droit, l'autorité cantonale de recours s'est référé à la décision rendue par la CNA quant aux "effets invalidants de l'affection accidentelle" et a confirmé le taux d'invalidité fixé par l'office AI.
3.2 Le recourant reproche à la juridiction cantonale d'avoir établi les faits de façon manifestement inexacte et arbitraire en retenant que les syndromes d'apnées du sommeil et des jambes sans repos dont il souffre n'étaient pas invalidants. Il aurait été nécessaire, selon lui, de poser des questions complémentaires au docteur S._, notamment sur les limitations fonctionnelles induites par ces atteintes et une éventuelle diminution de la capacité de travail que celles-ci entraîneraient, comme l'avait préconisé le docteur F._ du Service médical régional AI (SMR) dans son avis du 24 avril 2006.
3.3 Les griefs du recourant sont fondés, dès lors que la façon de procéder de la juridiction cantonale n'est pas conforme au droit.
Tout d'abord, l'autorité judiciaire de première instance a implicitement admis que les syndromes d'apnées du sommeil et des jambes sans repos limitaient la capacité de travail du recourant (en mentionnant la possibilité d'une amélioration "jusqu'à que cette atteinte n'affecte plus la capacité de travail de manière quantifiable"). Elle n'a cependant fait aucune constatation propre quant à l'étendue de cette limitation de la capacité de travailler du recourant, que ce soit dans l'activité exercée jusqu'à la fin du mois de juin 2000 ou une activité autrement exigible. A cet égard, et contrairement à ce qu'expose le jugement entrepris dans la partie "en fait" (p. 5) pour décrire le contenu du rapport du docteur S._, celui-ci n'a pas considéré que l'assuré pouvait travailler à 100% dans une activité adaptée. Si le médecin a effectivement indiqué que le recourant n'était plus en mesure de travailler comme cimentier et qu'on pouvait exiger de lui qu'il exerce une activité épargnant les genoux ("immobilité"), il n'a pas répondu à la question de savoir dans quelle mesure cette activité pouvait être exercée (heures par jour), tout en mentionnant qu'il fallait s'attendre à une diminution de rendement. L'affirmation - déjà exprimée de façon pour le moins surprenante par le médecin du SMR dans son avis du 21 juillet 2007 - selon laquelle le docteur S._ aurait considéré que l'assuré pouvait travailler à 100% apparaît manifestement inexacte, voire insoutenable. Faute de constatations de la juridiction cantonale quant aux conséquences des atteintes en cause sur la capacité de travail du recourant, on ignore donc dans quelle mesure celle-ci est diminuée. Le dossier ne contient au demeurant aucune évaluation médicale suffisante sur ce point, l'avis du docteur F._ qui repose sur une lecture erronée de celui de son confrère S._ n'étant pas pertinent.
En ce qui concerne par ailleurs les mesures médicales envisagées, le neurologue a certes indiqué que l'assuré n'était pas traité de façon optimale pour le syndrome des jambes sans repos - un traitement d'agoniste dopaminergique à doses croissantes n'ayant pas donné les résultats escomptés -, tandis que le syndrome des hypopnées du sommeil n'avait pas du tout été soigné alors qu'un traitement dont on pouvait attendre une amélioration de la fatigue diurne était justifié. Ni son rapport, ni les autres pièces médicales au dossier ne permettent cependant d'établir la nature exacte des traitements envisagés ou de savoir si de nouvelles mesures thérapeutiques ont été entreprises. Le médecin du SMR avait dans un premier temps requis de l'intimé qu'il posât quatre questions au docteur S._ portant tant sur les limitations fonctionnelles des atteintes en cause - qui pouvaient selon lui entraîner des troubles du sommeil importants, avec fatigabilité et troubles de la concentration pendant la journée -, que sur la capacité de travail de l'assuré et la nature de mesures thérapeutiques éventuellement mises en place, sans que ces questions n'eussent apparemment été transmises au neurologue. La juridiction cantonale ne pouvait donc, faute d'informations probantes à ce sujet, retenir que le syndrome d'apnées du sommeil avec syndrome des jambes sans repos n'était "pas invalidant au sens de la loi", sans tenir compte des exigences posées par l'<ref-law>. On rappellera qu'à teneur de cette disposition, ce n'est qu'après une sommation légale que les prestations d'assurance peuvent éventuellement être réduites ou refusées si l'assuré se soustrait ou s'oppose, ou encore ne participe pas spontanément, dans les limites de ce qui peut être exigé de lui, à un traitement raisonnablement exigible et susceptible d'améliorer notablement sa capacité de travail.
Dans ces circonstances, il convient d'admettre le recours et de renvoyer la cause à l'intimé pour qu'il examine quelle est la nature du traitement envisagé pour améliorer la capacité de travail du recourant et procède, le cas échéant, conformément à l'<ref-law>. Dans le cadre de ce renvoi, il lui appartiendra également d'éclaircir le point de savoir si et dans quelle mesure le syndrome des hypopnées du sommeil et celui des jambes sans repos ont influencé de manière négative la capacité de travail du recourant. Une fois l'instruction complétée, il statuera à nouveau sur le droit du recourant à une rente de l'assurance-invalidité.
4. La procédure est onéreuse (<ref-law>). Les frais judiciaires sont mis à la charge de l'intimé qui succombe (<ref-law>). Le recourant, qui obtient gain de cause, a droit à des dépens de la part de l'intimé (<ref-law>).

Par ces motifs, le Tribunal fédéral prononce:
1. Le recours est admis. Le jugement du Tribunal des assurances du canton de Vaud du 18 novembre 2008 et la décision de l'Office de l'assurance-invalidité pour le canton de Vaud du 2 novembre 2007 sont annulés, la cause étant renvoyée à cet office pour complément d'instruction et nouvelle décision conformément aux considérants.
2. Les frais judiciaires, arrêtés à 500 fr., sont mis à la charge de l'intimé.
3. L'intimé versera au recourant la somme de 2800 fr. à titre de dépens pour la dernière instance.
4. Le Tribunal cantonal vaudois, Cour des assurances sociales, statuera sur les frais et dépens au regard de l'issue du procès en dernière instance.
5. Le présent arrêt est communiqué aux parties, à la Cour des assurances sociales du Tribunal cantonal du canton de Vaud et à l'Office fédéral des assurances sociales.
Lucerne, le 14 août 2009
Au nom de la IIe Cour de droit social
du Tribunal fédéral suisse
Le Président: La Greffière:
Meyer Moser-Szeless