There are 2 ways to search available packages from cli on Ubuntu:

  1. apt-cache
  2. apt

Each gives different output formats; apt-cache is like lean and one line. apt includes more info and highlights the package name. I usually prefer apt.

For instance lets search NeoVim and see the results:

apt-cache

user@host:~$ apt-cache search neovim
lua-nvim - Lua client for Neovim
lua-nvim-dev - Lua client for Neovim
neovim - heavily refactored vim fork
neovim-qt - neovim client library and GUI
neovim-runtime - heavily refactored vim fork (runtime files)
python-neovim - Python2 library for scripting Neovim processes through its msgpack-rpc API
python3-neovim - Python3 library for scripting Neovim processes through its msgpack-rpc API
ruby-neovim - Ruby client for Neovim

apt

user@host:~$ apt search neovim
Sorting... Done
Full Text Search... Done
lua-nvim/bionic 0.2.1-1-1~ubuntu18.04.1~ppa2 amd64
  Lua client for Neovim

lua-nvim-dev/bionic 0.2.1-1-1~ubuntu18.04.1~ppa2 amd64
  Lua client for Neovim

neovim/bionic,now 0.4.3-3~ubuntu18.04.1~ppa1 amd64 [installed]
  heavily refactored vim fork

neovim-qt/bionic 0.2.8-3 amd64
  neovim client library and GUI

neovim-runtime/bionic,bionic,now 0.4.3-3~ubuntu18.04.1~ppa1 all [installed,automatic]
  heavily refactored vim fork (runtime files)

python-neovim/bionic,bionic 0.2.6-3ppa1~ubuntu18.04.2 all
  Python2 library for scripting Neovim processes through its msgpack-rpc API

python3-neovim/bionic,bionic,now 0.2.6-3ppa1~ubuntu18.04.2 all [installed]
  Python3 library for scripting Neovim processes through its msgpack-rpc API

ruby-neovim/bionic,bionic 0.7.1-1 all
  Ruby client for Neovim

Info

Also you can pipe the outputs to less if it gives a lot of results.

All done!