> If the market is efficient (and it isn't, but it can be) then following a buyback, one would expect the market capitalization of the company to be smaller, as the company has paid out money.

The company's cash flow is the same, but there are fewer outstanding shares, so earnings per share goes up. Earnings per share matters because when it increases that implies that future dividends per share will also increase.

If investors expect higher future dividends, that means that the stock is worth more, so it goes up.